Ir para o conteúdo
MACkie

Problema com Grafos

Mensagens Recomendadas

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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação 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. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.