Ir para o conteúdo
MACkie

Problema com Grafos

Mensagens Recomendadas

MACkie    0
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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
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?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
MACkie    0
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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
mogers    14
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

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


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade