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

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.

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 .

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.

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.

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.

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.

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

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.

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ó.

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

Por exemplo:

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.