Wenn wir ein Graphenproblem haben, woher wissen wir, ob wir den Bfs-Algorithmus oder den Dfs-Algorithmus verwenden müssen??? oder wann wir den dfs-Algorithmus oder den bfs-Algorithmus verwenden sollen. Was sind die Unterschiede und Vorteile des einen gegenüber dem anderen?
Antworten
Zu viele Anzeigen?
BFS wird je nach Verzweigungsfaktor mehr Speicherplatz benötigen... BFS ist jedoch ein vollständiger Algorithmus... das heißt, wenn Sie ihn verwenden, um etwas in der geringstmöglichen Tiefe zu suchen, wird BFS Ihnen die optimale Lösung liefern. Die Raumkomplexität von BFS ist O(b^d) ... der Verzweigungsfaktor auf die Tiefe erhöht (kann eine Menge Speicher sein).
DFS hingegen ist viel besser, was den Platz angeht, aber es kann eine suboptimale Lösung finden. Das heißt, wenn Sie nur nach einem Weg von einem Knotenpunkt zu einem anderen suchen, finden Sie möglicherweise die suboptimale Lösung (und bleiben dort stehen), bevor Sie den wirklich kürzesten Weg finden. Die Komplexität des DFS-Raums ist O(|V|) ... was bedeutet, dass der größtmögliche Speicherplatz der längste mögliche Weg ist.
Sie haben die gleiche zeitliche Komplexität.
Was die Implementierung betrifft, so wird BFS normalerweise mit Queue während das DFS eine Stack .
dhoss
Punkte
160
Breite zuerst sucht zuerst nach Geschwistern. Tiefe zuerst sucht natürlich zuerst nach Kindern. Also, ich denke, es würde davon abhängen, welche Art der Suche Sie suchen, um zu tun. Beziehung Typ sucht über Felder würde wahrscheinlich eignen sich für bfs, wo hierarchische (Bäume, Ordner, Ränge, etc.) würde mehr als dfs geeignet sein.
madCode
Punkte
3577
Beide Graphen-Traversalen versprechen eines: eine vollständige Durchquerung des Graphen, wobei jeder Knoten des Graphen besucht wird. Wenn Sie nur wenig Speicherplatz zur Verfügung haben, ist DFS eine gute Wahl, da BFS viel Platz benötigt. Die Wahl zwischen diesen beiden Verfahren hängt also von Ihren Anforderungen ab.
Möchten Sie die (stark/)verbundenen Komponenten des Graphen finden? Oder das Labyrinth lösen? Oder Sudoku? Verwenden Sie DFS. Wenn Sie genau hinsehen, sind Pre-Order, Post-Order und In-Order allesamt Varianten der DFS. Also, ja, das sind einige interessante Anwendungen.
BFS, wenn Sie testen wollen, ob ein Graph zweistufig ist, den kürzesten Weg zwischen zwei Knoten finden wollen oder Anwendungen, die solche Aufgaben erfordern.
anshu shrivastavs
Punkte
21
In bfs wird eine Warteschlange verwendet, während in dfs ein Stapel verwendet wird, um Eckpunkte entsprechend der Graphendurchquerung zu speichern.
2- in bfs wird der Prozess Ebene für Ebene durchgeführt (entsprechend dem gerichteten oder ungerichteten Graphen) während in dfs der Prozess in der Tiefe durchgeführt wird (der Prozess des ersten Besuchs des Wurzelknotens und ein anderer ist weit zu tun und dann Backtracking vom letzten Knoten zum Wurzelknoten anzuwenden).
