Pourquoi DFS et non BFS pour trouver un cycle dans les graphes

Question

Principalement, DFS est utilisé pour trouver un cycle dans les graphes et non BFS. Des raisons ? Les deux peuvent trouver si un nœud a déjà été visité lors de la traversée de l'arbre / du graphe.

Answer 1

La recherche en profondeur (depth first search) est plus efficace en termes de mémoire que la recherche en largeur (breadth first search) car vous pouvez faire demi-tour plus tôt. Il est également plus facile à implémenter si vous utilisez la pile d'appels, mais cela dépend du fait que le chemin le plus long ne dépasse pas la pile.

Aussi, si votre graphe est orienté, vous devez non seulement vous rappeler si vous avez visité un nœud ou pas, mais aussi comment vous êtes arrivé là. Sinon, vous pourriez penser avoir trouvé un cycle alors qu'en réalité, vous avez simplement deux chemins séparés A->B, ce qui ne signifie pas qu'il y a un chemin B->A. Par exemple,

Si vous utilisez la recherche en largeur (BFS) en partant de 0, il détectera la présence d'un cycle alors qu'en réalité il n'y en a pas.

Avec une recherche en profondeur, vous pouvez marquer les nœuds comme visités en descendant et les démarquer en remontant. Consultez les commentaires pour une amélioration des performances de cet algorithme.

Pour le meilleur algorithme pour détecter les cycles dans un graphe orienté, vous pouvez regarder l'algorithme de Tarjan.

Answer 2

1. DFS est plus facile à implémenter
2. Une fois que DFS trouve un cycle, la pile contiendra les nœuds formant le cycle. Ce n'est pas le cas pour BFS, donc vous devez faire un travail supplémentaire si vous voulez également imprimer le cycle trouvé. Cela rend DFS beaucoup plus pratique.

Answer 3

Je ne sais pas pourquoi une question aussi ancienne est apparue dans mon flux, mais toutes les réponses précédentes sont mauvaises, donc...

DFS est utilisé pour trouver des cycles dans des graphes dirigés, car cela fonctionne.

Dans un DFS, chaque sommet est "visité", où visiter un sommet signifie :

1. Le sommet est démarré

2. Le sous-graphe accessible à partir de ce sommet est visité. Cela inclut le traçage de tous les bords non traçés qui sont accessibles à partir de ce sommet, et la visite de tous les sommets accessibles non visités.

3. Le sommet est terminé.

La caractéristique critique est que tous les bords accessibles à partir d'un sommet sont traçés avant que le sommet ne soit terminé. C'est une caractéristique du DFS, mais pas du BFS. En fait, c'est la définition du DFS.

En raison de cette caractéristique, nous savons que lorsque le premier sommet dans un cycle est démarré :

1. Aucun des bords du cycle n'a été traçé. Nous le savons car on ne peut y accéder que depuis un autre sommet du cycle, et nous parlons du premier sommet à démarrer.
2. Tous les bords non traçés accessibles à partir de ce sommet seront traçs avant qu'il ne soit terminé, et cela inclut tous les bords du cycle, car aucun d'entre eux n'a encore été traçé. Par conséquent, s'il y a un cycle, nous trouverons un bord de retour au premier sommet après qu'il soit démarré, mais avant qu'il ne soit terminé; et
3. Comme tous les bords traçés sont accessibles à partir de chaque sommet démarré mais non terminé, trouver un bord vers un tel sommet démarré-mais-non-terminé indique toujours un cycle.

Ainsi, s'il y a un cycle, alors nous sommes assurés de trouver un bord vers un sommet démarré-mais-non-terminé (2), et si nous trouvons un tel bord, alors nous sommes assurés qu'il y a un cycle (3).

C'est pourquoi DFS est utilisé pour trouver des cycles dans des graphes dirigés.

Le BFS ne fournit aucune garantie, donc cela ne fonctionne tout simplement pas. (nonobstant les algorithmes de détection de cycle parfaitement valables qui incluent BFS ou similaire en tant que sous-procédure)

En revanche, un graphe non dirigé a un cycle chaque fois qu'il existe deux chemins entre n'importe quel couple de sommets, c'est-à-dire lorsqu'il ne s'agit pas d'un arbre. Cela est facile à détecter pendant BFS ou DFS -- Les bords tracés vers de nouveaux sommets forment un arbre, et tout autre bord indique un cycle.

Answer 4

Un BFS pourrait être raisonnable si le graphe est non orienté (allez-y pour montrer un algorithme efficace utilisant BFS qui signalerait les cycles dans un graphe orienté!), où chaque "arête de croisement" définit un cycle. Si l'arête de croisement est {v1, v2}, et que la racine (dans l'arbre BFS) contient ces nœuds est r, alors le cycle est r ~ v1 - v2 ~ r (~ est un chemin, - une seule arête), qui peut être signalé presque aussi facilement qu'avec DFS.

La seule raison d'utiliser un BFS serait si vous savez que votre graphe (non orienté) va avoir des chemins longs et une petite couverture de chemin (en d'autres termes, profond et étroit). Dans ce cas, BFS nécessiterait proportionnellement moins de mémoire pour sa file d'attente que la pile de DFS (tous deux sont bien sûr linéaires).

Dans tous les autres cas, DFS est clairement le gagnant. Il fonctionne sur les graphes dirigés et non dirigés, et il est triviale de signaler les cycles - il suffit de concaténer toute arête arrière au chemin de l'ancêtre au descendant, et vous obtenez le cycle. Dans l'ensemble, beaucoup mieux et plus pratique que BFS pour ce problème.

Answer 5

BFS ne fonctionnera pas pour un graphe dirigé pour trouver des cycles. Considérez A->B et A->C->B comme des chemins de A à B dans un graphe. BFS dira qu'une fois que B est atteint en suivant l'un des chemins. En continuant à voyager sur le prochain chemin, il dira que le noeud marqué B a été trouvé à nouveau, donc, il y a un cycle. Il est clair qu'il n'y a pas de cycle ici.