Travessias BFS e DFS

[for]

Boas pessoal 🙂

Alguém me consegue explicar qual seria o resultado da travessia BFS e DFS deste grafo:

Ponto de partida por exemplo o A qual seria o resultado?

Estive a ver alguns exemplo das travessias BFS e DFS mas quase todos são de árvores e sem direçoes, se alguem me poder ajudar agradecia.

Cumps 😉

[HappyHippyHippo]

mas queres que te expliquem o que é o BFS e o DFS, ou queres o resultado ?

[for]

O resultado nem é tão importante, era uma explicação, talvez com o resultado seja mais fácil explicar não sei.

Obrigado pela ajuda desde ja 😉

[HappyHippyHippo]

em vez de estar aqui a escrever explicações de metro e meio

BFS : https://en.wikipedia.org/wiki/Breadth-first_search

DFS : https://en.wikipedia.org/wiki/Depth-first_search

[for]

Mas nestes casos não existe direçoes, apenas é aplicado o que eu percebo sobre o BFS e DFS eu queria saber em casos como o que perguntei aqui, o que influencia na sua resolução.

[HappyHippyHippo]

Que?

Qual a diferenca de um grafo direccionado ou nao na aplicacao do algoritmo?

[for]

Sim, gostava de saber a diferença que um grafo direccionado tem na resolução do algoritmo.

Pq bfs é em largura e dfs em profundidade senão existir direcções é fácil perceber a sua resolução pq é seguir uma sequência.

[HappyHippyHippo]

Prontos, agora a unica diferenca e que essa sequencia podera "ignorar" algumas ligacoes porque por esta nao se encontrar definida na direccao a ser considerada

[for]

Se me conseguisses dar um exemplo mesmo que não seja este grafo ficava agradecido, em largura acho que ja cheguei la em profundidade não consigo perceber muito bem a logica.

Obrigado pela ajuda 😉

[HappyHippyHippo]

Agora e difícil porque estou no telemovel, so mais tarde

[for]

Ok quando poderes, obrigado 😉

[HappyHippyHippo]

só uma pergunta : conseguirias resolver se o grafo não fosse direccionado ?

[for]

Na minha ideia BFS sem direções:

Resultado:ADCBGEHFI

DFS:

Resultado:ABEIHGDFCD

So mais uma coisa que tambem pode estar a confundir, o resultado pode variar conforme a ordem que escolho certo?

Edited January 25, 2016 at 05:50 PM by for

[HappyHippyHippo]

vou supor que sabes o algoritmo apesar que o DFS estar errado, mas perece ser distração.

agora se eu disser que um grafo "sem direções" é um grafo direcionado em que todas as ligações são bidirecionais ? achas que percebes assim o problema ?

[for]

Dfs esta errado? pode ser distracção, vou ja verificar, uma das diferenças esta principalmente em que um utiliza uma queue e vamos fazemos "FIFO" e o outro é uma STACK é que fazemos "LIFO".

Ordem pela qual escolhemos o no faz diferença no resultado mas não invalida se esta errado ou não certo?

[HappyHippyHippo]

uma das diferenças esta principalmente em que um utiliza uma queue e vamos fazemos "FIFO" e o outro é uma STACK é que fazemos "LIFO".

isso é para a resolução programática do problema.

estou a tentar ver se consegues perceber a engrenagem do algoritmo antes de chegar a isso

Ordem pela qual escolhemos o no faz diferença no resultado mas não invalida se esta errado ou não certo?

certo

[for]

Eu utilizo um pouco a forma programática para resolver. Talvez esteja ai o meu problema no DFS.

Por exemplo para a resolução sem direções começo no A a seguir vou para outro no exemplo D, eu nesta fase tenho de colocar tdos os nos abaixo do A ou apenas um e agora analiso outro no a seguir de D?

[HappyHippyHippo]

Por exemplo para a resolução sem direções começo no A a seguir vou para outro no exemplo D, eu nesta fase tenho de colocar tdos os nos abaixo do A ou apenas um e agora analiso outro no a seguir de D?

suponho que estevas a falar da DFS, e sim, ao processares o nó D, então terás de processar um nó "atingivel" por D que ainda não tenha sido processado, neste caso, C ou G

[for]

Acho que já consegui perceber a lógica. obrigado pela ajuda 🙂