Breite zuerst oder Tiefe zuerst Suche nach einem Kind in einer bestimmten Tiefe zu finden?

Question

Ich weiß, dass es hier viele Fragen zu Breadth First Search vs. Tiefensuche gibt, aber ich denke, dass meine Situation ein wenig anders ist.

Ich habe einen verwurzelten Baum, in dem jeder Knoten 0, 1 oder 2 Kinder (mit der erwarteten Zahl 1) haben kann. Angesichts einer großen Zahl n, möchte ich einen Pfad durch den Baum der Länge n finden.

Es scheint klar, dass Tiefe zuerst sollte der beste Weg, dies zu tun, aber ich bin mir nicht so sicher. Die Breite des Baumes ist sehr klein, was normalerweise ein Grund ist, die Breite der ersten Suche zu verwenden. Wenn ich Tiefensuche verwende, könnte ich am Ende in einen Teilbaum gehen, dessen Höhe sehr nahe bei n liegt, aber kleiner als n. In diesem Fall werde ich viel Zeit verschwenden einen Baum durchquert, die mich nicht möglicherweise die Antwort geben kann ich

wollen

Answer 1

1. DFS wird immer effizienter als BFS für Ihr Ziel. da BFS über alle Knoten in Tiefe 1 iteriert, dann alle Knoten in Tiefe 2, usw., um einen Pfad der Länge n zu finden, wird BFS zuerst alle Pfade im Baum der Länge durchlaufen < = n- 1. Im absoluten schlimmsten Fall wird DFS dasselbe tun, bis der angeforderte Pfad gefunden wird, aber im Allgemeinen wird DFS meines Erachtens weitaus effizienter sein.

2. Ich weiß, dass das nicht immer möglich ist, aber Sie können Ihre Baumimplementierung so ändern, dass jeder Knoten die Länge seines Unterbaums (den Maximalwert zwischen den Unterknoten des Knotens) enthält, damit wird Ihr Problem gelöst und ist sehr einfach zu pflegen während der regelmäßigen einfügen \ entfernen usw.