Ola a todos,
Estou com um problema bem chato. Uma vez implementei um programa que dado um grafo qualquer e um ponto inicial e final, ele nos mostra o caminho que deve ser percorrido para se chegar do ponto inicial ao ponto final. Fiz o programa utilizando busca em largura e busca em profundidade.
Porém o programa que fiz foi em C#, e utilizando listas para representar o grafo. Agora entra o grande problema.
Estou tentando codificar em C só que utilizando a representação do grafo em Matrizes, da seguinte forma: dado uma quantidade de nós que o grafo irá ter, criamos uma matriz com a dimensão quadrada, onde o tamanho é o nó. Ou seja, num grafo com 2 nós, temos uma matriz 2x2.
Olhem a matriz abaixo para entenderem:
0 1
1 0
Cada linha representa um nó, e cada coluna também representa um nó. Quando se tem 0 significa que não tem conexão; quando se tem 1 significa que se tem conexão. Ou seja, no nossso exemplo, o nó 0 não tem conexão com o nó zero, mas tem conexão com o nó 1. O nó 1 tem conexão com o nó 0 mas não tem conexão com o nó 1.
Este problema ja esta resolvido, só não consegui pensar em uma lógica para achar o caminho entre um ponto a para o ponto b.
Alguém tem alguma ideia? Não estou pedindo código pronto, já seria pedir demais, só estou pendindo sugestões de implementanção.
Abraços,
progArt.