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

MACkie

Problema com Grafos

4 mensagens neste tópico

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora