Duvida Matriz de Adjacencia e Grafos Conexos

Smalltalk Membro desde: 03/09/2006 14:23:34 Mensagens: 4 Offline

E aew galera fmza...
estou com uma tremenda duvida
naum estou conseguindo fazer um algoritmo para verificar as componentes conexas de um grafo....

tipo dado uma determinada matriz de adjacencia essa por exemplo:

V0 V1 V2 V3
V0 || 0 || 1 || 1 || 0 ||
V1 || 1 || 0 || 1 || 0 ||
V2 || 1 || 1 || 0 || 0 ||
V3 || 0 || 0 || 0 || 0 ||

queria achar as componentes conexas....

ou seja teria que aparecer assim...
>componente conexa: V0 V1 V2
>componene conexa: V3

se alguem poder me ajudar....
estou desesperado...
valew

Debugger Membro desde: 10/09/2006 12:02:04 Mensagens: 61 Offline

Espero ter entendido seu problema.. Mas eu faria assim:

- Fazia dois "for" para percorrer toda a matriz...
- Comparava cada posição da matriz se o valor fosse != 0
- Se fosse diferente, comparava a linha do valor da coluna q eu encontrei que era !=0 pra verificar se nessa linha havia mais algum valor != 0 e ia armazenando esses valores em um vetor sem repetir os valores nesse vetor...
- Caso não encontrasse nenhum valor !=0 é pq a componente conexa era o proprio valor da linha
- Fazia isso até olhar toda a matriz...

Não sei se fui bem explicativo mas pelo q entendi do seu problema isso aí dá certo, resta vc ver direitinho q eu disse

PS: Trabalho pra amanhã e vc deixou pra fazer hj, né?

Smalltalk Membro desde: 03/09/2006 14:23:34 Mensagens: 4 Offline

e aew daniel...
valeu pela ajuda...
pior que o trabalho eh pra amanha mesmo...
mas eu to a muito tempo fazendo....eu demorei muito pra fazer umas outras partes mais básicas...estou a semana inteira fazendo...mas como eu sou muito iniciante em java eu apanho em coisas basicas....e agora que eu comecei a usar os foruns =(....

devia ter usado antes....

bom mas eu vou tentando fazer aki...

valew

O algoritmo de busca em profundidade encontra todos os vértices alcançáveis a partir de um determinado vértice. Então, pra encontrar as componentes conexas de um grafo, inicie uma busca em profundidade a partir de um vértice qualquer; os vértices visitados nessa busca formam a primeira componente conexa. Escolha então um vértice não-visitado e faça outra busca a partir dele, e vc encontrará a segunda componente conexa. Repita o processo até que não haja vértices não visitados.

Notícias, artigos e o maior fórum brasileiro sobre Java