Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

MACkie

Problema com Grafos

Recommended Posts

MACkie

Boas,

Eu e grafos é "serious business". Não percebo nada daquilo. E sim, já li o tutorial. Essa parte eu percebo. O que eu não percebo é como programar um - em C# ou Java.

Preciso disso para um trabalho e tou completamente às aranhas.

Se alguém tiver um grafo codificado em C# ou Java agradecia muito. De preferência dos ponderados e orientados - É para depois aplicar o algoritmo de Bellman-Ford.

Cumprimentos,

MACkie


private void doNotDisturb(string motive)if(motive.compareTo(somethingReallyImportant) == 0)pay attention;else//do nothing

Share this post


Link to post
Share on other sites
mogers

Expõe aqui o que não percebes como implementar. Depois de perceber o artigo sobre grafos, penso que essa parte seria natural...

O que é que entendeste da representação do grafo através de matriz de adjacencias, lista de adjacencias ou lista de arestas?


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites
MACkie

O que eu não percebo é mesmo como implementar tudo. Como implemento os nós, os ramos, os pesos, a orientação...

Eu percebi essa parte da matriz de adjacências e da lista de arestas, o meu professor também falou disso. Mas como é que eu, a programar, implemento isso? O programa tem que gerar aleatoriamente o numero de ramos para cada nó e o seu peso...

Tou a embirrar com isto.

Cumprimentos,

MACkie


private void doNotDisturb(string motive)if(motive.compareTo(somethingReallyImportant) == 0)pay attention;else//do nothing

Share this post


Link to post
Share on other sites
mogers

Tendo um gravo com N vértices (ou nós), considera o exemplo de matriz de adjacencias:

podes usar uma matriz N*N do tipo de dados que representar o peso de uma ligação.  matriz[ a ][ b ] = peso da aresta (ligação) a -> b. Quando o grafo só tem pesos positivos, costumo usar pesos negativos para saber que a ligação não existe. Contudo, como pretendes usar o Bellman-Ford subentendo que o grafo tem pesos negativos, por isso sugiro o uso de uma matriz de booleanos auxiliar que hasEdge[ a ][ b ] tem o valor true ou false consoante existe ligação entre a e b ou não.

Eu sei mesmo muito pouco de c# mas penso que seria algo como

double [,] matriz = new double[ N , N ];
bool [,] hasEdge = new bool[ N , N ];
// popular a matriz
// i = vertice 1 gerado aleatoriamente
// j = vertice 2 gerado aleatoriamente
// matriz[i,j] = custo gerado aleatoriamente
// hasEdge[i,j] = true;
// ...

for (i = 0 ; i < N ; i++) // percorrer todos os vertices e para cada um
    for (j = 0 ; j < N ; j++) // verificar se que colunas da respectiva linha da matriz estao preenchidos 
         if ( hasEdge[i,j] )
              // existe ligação i->j
              // faz qualquer coisa


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.