A Depth-First- Suche ist ein Algorithmus, prozedural sucht ein Graph oder eine Baumstruktur durch Reisen so weit unten in der Struktur , wie sie können, bevor die Sicherung . Die Zeit, die der Algorithmus zum Ende kommt , hängt von der Anzahl der Knoten in dem Graphen . Im schlimmsten Fall muss der Algorithmus besuchen jeden Knoten im Graphen . Baumgraphen
Im Rahmen von Graphen , ist ein Baum ein Graph, in dem jeder Knoten mit Ausnahme der Herkunft "root "-Knoten hat einen einzigen übergeordneten Knoten, dessen Linie geht zurück auf den Root-Knoten . Die Grafik bildet eine Struktur ähnlich der eines Weihnachtsbaumes , schrittweise erweitert und das Hinzufügen neuer Knoten und Kinder auf jeder Ebene. In einem Baum, ist die Zahl der Kinder jeder Knoten des Baumes " Verzweigungsfaktor . " Die Zahl der Generationen im Baum ist der Baum der " Tiefe ".
Tiefensuche
Tiefensuche ist eine Methode des Suchens durch einen Baum , in dem der Algorithmus geht den Baum , bis sie den Zielknoten findet . Ausgehend von der Root-Knoten , geht der Algorithmus auf die nächste Kind und dann das Kind Enkel , den Prozess wiederholen, bis es eine kinderlose "leaf" Knoten findet . Nachdem es diesen Knoten findet , geht es zurück , bis es eine ungeprüfte Knoten findet . Wenn es keine weiteren untersuchten Knoten sind , stoppt er .
Algorithm Zeit Komplexität
Die Zeit, einen Baum über Tiefensuche durchlaufen hängt von der Anzahl der Knoten in dem Graphen und Kanten zwischen ihnen. Im ungünstigsten Fall muss der Algorithmus durch jeden Knoten und entlang jeder Kante fahren , so dass die benötigten Zeit ist die Anzahl der Knoten und die Anzahl der Kanten , oder " V + E. " Für einen Baum , die Anzahl der Kanten ist gleich der Knoten minus eins ist, so ist die Gesamtzeit " 2V - . 1", wenn jeder Knoten des Graphen die gleiche Anzahl von Kindern - eine Konstante Verzweigungsgrad - dann ist diese Zeit gleich dem Faktor ist . angehoben, um die Macht des Baumes Tiefe
Andere Überlegungen
Bei der Umsetzung jeder Algorithmus hängt die Geschwindigkeit des Algorithmus auf zwei Faktoren : die Anzahl der Berechnungen muss es machen und die erforderliche Zeit, um die benötigten Ressourcen zugreifen zu laufen - in der Regel Speicher . Je mehr Speicher ein Programm benötigt , desto länger dauert es zu laufen. Eine Tiefensuche müssen die vorherigen Knoten besuchte er erinnern , so im schlimmsten Fall viel Speicher es erfordert, ist gleich der Anzahl der Knoten im Baum.
