Jump to content
for

[Resolvido] Travessias BFS e DFS

Recommended Posts

for

Boas pessoal :)

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

uIWEHxc.jpg?1

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 ;)

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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 ;)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
HappyHippyHippo

Que?

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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 ;)

Share this post


Link to post
Share on other sites
HappyHippyHippo

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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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 by for

Share this post


Link to post
Share on other sites
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 ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.