Busca em Largura em grafo representado com Matriz

progArt · 6 de julho de 2009

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.

ningen · 7 de julho de 2009

Não seria o mesmo caso de você criar uma entrutura, passar os dados da matriz pra uma lista dessa estrutura, e depois aplicar a mesma lógica que usou em C#?

Pelo que entendi, você tá criando um tipo de tabela assim:


Nós:   a b c d
    a  0 1 1 0
    b  1 0 1 0
    c  ...
    d  ...

Escolhe um nó inicial, pega os dados da coluna dele e joga numa estrutura, como uma árvore, por exemplo. Você terá uma árvore com um nível... pra cada folha dessa árvore você repete isso, até ter todos os níveis.

Se a pergunta não foi essa, desculpa.

progArt · 7 de julho de 2009

Lunik,

É exatamente o que você falou que não quero usar...

Eu quero resolver este problema da forma mais primitiva possível, ou seja, trabalhando somente com os indices da matriz e vetores auxiliares ou até mesmo matrizes auxiliares. Não quero usar nenhum tipo de estrutura dinâmica, pois desta forma eu ja fiz.

As vezes acho que nem é possível fazer uma solução da forma que penso, mas desafios sempre é bom (eu gosto).

valeu pela ajuda. Se eu conseguir resolver eu retorno com a resposta no forum.

Estou aberto ainda para novas sugestões.

Abraços,

progArt.