Por que DFS e não BFS para encontrar o ciclo em gráficos

86

Predominantemente, DFS é usado para encontrar um ciclo em gráficos e não BFS. Quaisquer razões? Ambos podem descobrir se um nó já foi visitado ao percorrer a árvore / gráfico.

má companhia
fonte
5
Em gráficos direcionados, apenas DFS pode ser usado para detectar um ciclo; mas em gráficos não direcionados ambos podem ser usados.
Hengameh

Respostas:

74

A primeira pesquisa em profundidade é mais eficiente em termos de memória do que a primeira pesquisa em amplitude, pois você pode voltar mais cedo. Também é mais fácil de implementar se você usar a pilha de chamadas, mas isso depende do caminho mais longo, sem estourar a pilha.

Além disso, se o seu gráfico é direcionado , você não deve apenas lembrar se visitou um nó ou não, mas também como chegou lá. Caso contrário, você pode pensar que encontrou um ciclo, mas na realidade tudo o que você tem são dois caminhos separados A-> B, mas isso não significa que existe um caminho B-> A. Por exemplo,

Se você fizer o BFS a partir de 0, ele detectará se o ciclo está presente, mas na verdade não há ciclo.

Com uma primeira pesquisa em profundidade, você pode marcar os nós como visitados conforme você desce e desmarcá-los ao voltar. Veja os comentários para uma melhoria de desempenho neste algoritmo.

Para obter o melhor algoritmo de detecção de ciclos em um gráfico direcionado, você pode examinar o algoritmo de Tarjan .

Mark Byers
fonte
3
(Memória eficiente porque você volta atrás mais cedo, e mais fácil de implementar porque você pode apenas deixar a pilha cuidar do armazenamento da lista aberta em vez de mantê-la explicitamente.)
Âmbar
3
IMO, só é mais fácil se você puder confiar na recursão da cauda.
Hank Gay
2
"desmarque-os conforme você retrocede" - por sua própria conta e risco! Isso pode facilmente levar ao comportamento O (n ^ 2), especificamente um DFS interpretaria mal as bordas cruzadas como bordas de "árvore" (bordas de "árvore" também seriam um nome impróprio, já que não formariam mais uma árvore)
Dimitris Andreou
1
@Dimitris Andreo: Você pode usar três estados visitados em vez de dois para melhorar o desempenho. Com gráficos direcionados, há uma diferença entre 'Já vi este nó antes' e 'Este nó faz parte de um loop'. Com gráficos não direcionados, eles são equivalentes.
Mark Byers
Exatamente, você definitivamente precisa de um terceiro estado (para tornar o algoritmo linear), então você deve considerar revisar essa parte.
Dimitris Andreou
28
  1. DFS é mais fácil de implementar
  2. Assim que o DFS encontrar um ciclo, a pilha conterá os nós que formam o ciclo. O mesmo não é verdade para o BFS, então você precisa fazer um trabalho extra se quiser também imprimir o ciclo encontrado. Isso torna o DFS muito mais conveniente.
IVlad
fonte
11

Um BFS poderia ser razoável se o gráfico não fosse direcionado (seja meu convidado a mostrar um algoritmo eficiente usando BFS que relataria os ciclos em um gráfico direcionado!), Onde cada "borda cruzada" define um ciclo. Se a aresta cruzada for {v1, v2}e a raiz (na árvore BFS) que contém esses nós for r, o ciclo será r ~ v1 - v2 ~ r( ~é um caminho, -uma aresta única), o que pode ser relatado quase tão facilmente quanto no DFS.

A única razão para usar um BFS seria se você souber que seu gráfico (não direcionado) terá caminhos longos e cobertura de caminho pequeno (em outras palavras, profundo e estreito). Nesse caso, o BFS exigiria proporcionalmente menos memória para sua fila do que a pilha do DFS (ambos ainda lineares, é claro).

Em todos os outros casos, o DFS é claramente o vencedor. Ele funciona em gráficos direcionados e não direcionados, e é trivial relatar os ciclos - basta concatar qualquer borda posterior ao caminho do ancestral ao descendente e você obterá o ciclo. Em suma, muito melhor e prático do que o BFS para esse problema.

Dimitris Andreou
fonte
4

O BFS não funcionará para um gráfico direcionado na localização de ciclos. Considere A-> B e A-> C-> B como caminhos de A para B em um gráfico. BFS dirá que depois de percorrer um dos caminhos que B é visitado. Ao continuar a viajar para o próximo caminho, ele dirá que o nó marcado B foi encontrado novamente, portanto, um ciclo está lá. É claro que não há ciclo aqui.

Aditya Raman
fonte
Você pode explicar como o DFS identificará claramente que o ciclo não existe no seu exemplo. Concordo que o ciclo não existe no exemplo fornecido. Mas se formos de A-> B e A-> C-> B, encontraremos que B já foi visitado e seu pai é A não C ... e eu li que o DFS detectará o ciclo comparando o pai do elemento já visitado com o nó atual de qual direção estamos verificando neste momento. o que?
smasher
Tudo o que você mostrou aqui é que essa implementação específica não funciona, não que seja impossível com o BFS. Na verdade, é possível, embora exija mais trabalho e espaço.
Prune
@Prune: Todos os threads (eu acho) aqui estão tentando provar que o bfs não funcionará para detectar ciclos. Se você sabe como contrapor a prova, você deve fornecer a prova. Simplesmente dizer que os esforços são maiores não será suficiente
Aditya Raman
Como o algoritmo é fornecido nas postagens vinculadas, não acho apropriado repetir o esquema aqui.
Prune de
Não consegui encontrar nenhuma postagem vinculada, portanto, pedi o mesmo. Eu concordo com seu ponto sobre a capacidade do bfs e acabei de pensar na implementação. Obrigado pela dica :)
Aditya Raman
4

Não sei por que uma pergunta tão antiga apareceu no meu feed, mas todas as respostas anteriores são ruins, então ...

O DFS é usado para encontrar ciclos em gráficos direcionados, porque funciona .

Em um DFS, cada vértice é "visitado", onde visitar um vértice significa:

  1. O vértice é iniciado
  2. O subgráfico acessível a partir desse vértice é visitado. Isso inclui o rastreamento de todas as arestas não traçadas que são alcançáveis ​​a partir desse vértice e a visita a todos os vértices não visitados alcançáveis.

  3. O vértice está concluído.

A característica crítica é que todas as arestas alcançáveis ​​de um vértice são traçadas antes que o vértice seja concluído. Este é um recurso do DFS, mas não do BFS. Na verdade, esta é a definição de DFS.

Por causa desse recurso, sabemos que quando o primeiro vértice de um ciclo é iniciado:

  1. Nenhuma das bordas do ciclo foi traçada. Sabemos disso porque você só pode chegar até eles a partir de outro vértice do ciclo, e estamos falando sobre o primeiro vértice a ser iniciado.
  2. Todas as arestas não traçadas alcançáveis ​​a partir desse vértice serão traçadas antes de terminar, e isso inclui todas as arestas do ciclo, porque nenhuma delas foi traçada ainda. Portanto, se houver um ciclo, encontraremos uma aresta de volta ao primeiro vértice depois que ele for iniciado, mas antes de terminar; e
  3. Uma vez que todas as arestas traçadas são alcançáveis ​​a partir de cada vértice iniciado, mas não concluído, encontrar uma aresta para tal vértice sempre indica um ciclo.

Portanto, se houver um ciclo, temos a garantia de encontrar uma aresta para um vértice iniciado, mas não terminado (2), e se encontrarmos essa aresta, temos a garantia de que existe um ciclo (3).

É por isso que o DFS é usado para localizar ciclos em gráficos direcionados.

O BFS não oferece essas garantias, então simplesmente não funciona. (não obstante algoritmos de descoberta de ciclo perfeitamente bons que incluem BFS ou semelhante como um subprocedimento)

Um grafo não direcionado, por outro lado, tem um ciclo sempre que existem dois caminhos entre qualquer par de vértices, ou seja, quando não é uma árvore. Isso é fácil de detectar durante o BFS ou DFS - as arestas traçadas para novos vértices formam uma árvore, e qualquer outra aresta indica um ciclo.

Matt Timmermans
fonte
Na verdade, esta é a resposta mais (talvez a única) relacionada aqui, elaborando as razões reais.
plasmacel
2

Se você colocar um ciclo em um ponto aleatório em uma árvore, o DFS tenderá a acertar o ciclo quando estiver coberto por cerca de metade da árvore, e na metade do tempo já terá atravessado onde o ciclo vai, e na outra metade não ( e irá encontrá-lo em média na metade do resto da árvore), então ele avaliará em média cerca de 0,5 * 0,5 + 0,5 * 0,75 = 0,625 da árvore.

Se você colocar um ciclo em um ponto aleatório em uma árvore, o BFS tenderá a acertar o ciclo apenas quando for avaliado a camada da árvore naquela profundidade. Assim, normalmente você acaba tendo que avaliar as folhas de uma árvore binária de equilíbrio, o que geralmente resulta em uma avaliação maior da árvore. Em particular, 3/4 das vezes pelo menos um dos dois links aparece nas folhas da árvore, e nesses casos você deve avaliar em média 3/4 da árvore (se houver um link) ou 7 / 8 da árvore (se houver dois), então você já está na expectativa de pesquisar 1/2 * 3/4 ​​+ 1/4 * 7/8 = (7 + 12) / 32 = 21/32 = 0,656 ... da árvore sem nem mesmo adicionar o custo de busca em uma árvore com um ciclo adicionado fora dos nós de folha.

Além disso, o DFS é mais fácil de implementar do que o BFS. Portanto, é aquele a ser usado, a menos que você saiba algo sobre seus ciclos (por exemplo, os ciclos provavelmente estão próximos da raiz a partir da qual você pesquisa, ponto em que o BFS oferece uma vantagem).

Rex Kerr
fonte
Muitos números mágicos ali. Não concordo com os argumentos "DFS é mais rápido". Depende inteiramente da entrada e nenhuma entrada é mais comum do que outra neste caso.
IVlad
@Vlad - Os números não são mágicos. Eles são médias, são declarados como tal e são quase triviais de calcular, dadas as suposições que afirmei. Se a aproximação pela média for uma má aproximação, seria uma crítica válida. (E eu declarei explicitamente que se você pudesse fazer suposições sobre a estrutura, a resposta poderia mudar.)
Rex Kerr
os números são mágicos porque não significam nada. Você pegou um caso em que o DFS se sai melhor e extrapolou esses resultados para o caso geral. Suas afirmações são infundadas: "O DFS tenderá a acertar o ciclo quando estiver coberto por cerca de metade da árvore": prove. Sem falar que você não pode falar sobre ciclos em uma árvore. Uma árvore não tem um ciclo por definição. Eu simplesmente não vejo qual é o seu ponto. O DFS seguirá um caminho até chegar a um beco sem saída, então você não tem como saber quanto do GRAPH (NÃO da árvore) ele explorará em média. Você escolheu um caso aleatório que não prova nada.
IVlad
@Vlad - Todos os gráficos não cíclicos totalmente conectados não direcionados são árvores (sem raiz não direcionada). Eu quis dizer "um gráfico que seria uma árvore, exceto por um link espúrio". Talvez esta não seja a principal aplicação do algoritmo - talvez você queira encontrar ciclos em algum gráfico emaranhado que tenha muitos links que o tornam diferente de uma árvore. Mas se for semelhante a uma árvore, a média de todos os gráficos, qualquer nó tem a mesma probabilidade de ser a fonte do referido link espúrio, o que torna a cobertura de árvore esperada de 50% quando o link é atingido. Portanto, aceito que o exemplo pode não ter sido representativo. Mas a matemática deve ser trivial.
Rex Kerr de
1

Para provar que um gráfico é cíclico, você só precisa provar que ele tem um ciclo (a aresta apontando para si mesma direta ou indiretamente).

No DFS, pegamos um vértice de cada vez e verificamos se ele tem ciclo. Assim que um ciclo é encontrado, podemos omitir a verificação de outros vértices.

No BFS, precisamos manter o controle de muitas arestas de vértices simultaneamente e, na maioria das vezes, no final você descobre se ele tem ciclo. Conforme o tamanho do gráfico cresce, o BFS requer mais espaço, computação e tempo em comparação com o DFS.

Spiker
fonte
0

Isso depende se você está falando sobre implementações recursivas ou iterativas.

O DFS recursivo visita cada nó duas vezes. O Iterative-BFS visita cada nó uma vez.

Se quiser detectar um ciclo, você precisará investigar os nós antes e depois de adicionar suas adjacências - tanto quando você "inicia" em um nó quanto quando "termina" com um nó.

Isso requer mais trabalho no Iterative-BFS, então a maioria das pessoas escolhe o Recursive-DFS.

Observe que uma implementação simples de Iterative-DFS com, digamos, std :: stack tem o mesmo problema que Iterative-BFS. Nesse caso, você precisa colocar elementos fictícios na pilha para rastrear quando "terminar" de trabalhar em um nó.

Consulte esta resposta para obter mais detalhes sobre como Iterative-DFS requer trabalho adicional para determinar quando você "termina" com um nó (respondido no contexto de TopoSort):

Classificação topológica usando DFS sem recursão

Esperançosamente, isso explica porque as pessoas favorecem o DFS recursivo para problemas em que você precisa determinar quando "termina" o processamento de um nó.

Comunidade
fonte
Isso está totalmente errado, pois não importa se você usa recursão ou se elimina a recursão por iteração. Você pode implementar um DFS iterativo que visita cada nó duas vezes, assim como você pode implementar uma variante recursiva que visita cada nó apenas uma vez.
plasmacel
0

Você terá que usar BFS quando quiser encontrar o ciclo mais curto contendo um determinado nó em um gráfico direcionado.

Por exemplo:insira a descrição da imagem aqui

Se o nó fornecido for 2, há três ciclos em que ele faz parte de - [2,3,4], [2,3,4,5,6,7,8,9]& [2,5,6,7,8,9]. O mais curto é[2,3,4]

Para implementar isso usando BFS, você deve manter explicitamente o histórico de nós visitados usando estruturas de dados adequadas.

Mas para todos os outros fins (por exemplo: para encontrar qualquer caminho cíclico ou para verificar se um ciclo existe ou não), DFSé a escolha certa pelos motivos mencionados por outros.

Sameer
fonte