Diese Frage mag für Experten aber einfach seinEin Anfänger wie ich ist es wichtig. Meine Frage ist, gibt es irgendwelche Probleme mit Baum Traversalen, die von BFS, DFS und nicht in Ordnung, Pre-Order etc. gelöst werden können. Mit anderen Worten, wenn ich ein Baumproblem sehe, sollte ich nur an die 3 Baum Traversal-Methoden denken oder auch BFS, DFS
Antworten:
18 für die Antwort № 1Pre-Order-, In-Order- und Post-Order-Traversal sinddie drei verschiedenen Arten der Tiefensuche zuerst, die möglich sind. Es geht also nicht darum, ob man DFS oder eine dieser drei verwendet. Wenn Sie eine dieser drei Traversalen verwenden, dann sind Verwenden von DFS.
Ob es Fälle gibt, in denen BFS istvorzuziehen gegenüber DFS: Ja, da sind. Um beispielsweise den kürzesten Pfad zwischen zwei Knoten in einem ungewichteten Diagramm zu finden, können Sie BFS verwenden, da der erste von einem BFS gefundene Pfad der Pfad mit den wenigsten Kanten ist. Das gleiche gilt nicht für DFS.
2 für die Antwort № 2
Ein offensichtliches Beispiel, wo DFS nicht funktioniert und Sie haben BFS zu verwenden ist ein unendlich (oder zumindest beliebig) hoher Baum.