algorithm
Tiefe erste Suche

Einführung in die Tiefensuche

Die Tiefensuche ist ein Algorithmus zum Durchsuchen oder Durchsuchen von Baum- oder Diagrammdatenstrukturen. Man beginnt an der Wurzel und erforscht entlang jedes Zweiges so weit wie möglich, bevor es zurückgeht. Eine Version der Tiefensuche wurde im französischen Mathematiker Charles Pierre Trémaux aus dem 19. Jahrhundert als Strategie zur Lösung von Irrgärten untersucht.

Die Tiefensuche ist eine systematische Methode, um alle Scheitelpunkte zu finden, die von einem Quellscheitelpunkt aus erreichbar sind. Wie die Breitensuche durchsucht DFS eine verbundene Komponente eines bestimmten Diagramms und definiert einen Spannbaum. Die Grundidee der Tiefensuche besteht darin, jeden Rand methodisch zu untersuchen. Wir beginnen bei Bedarf von einem anderen Punkt aus. Sobald wir einen Scheitelpunkt entdeckt haben, beginnt DFS mit der Suche von diesem (im Gegensatz zu BFS, bei dem ein Scheitelpunkt in eine Warteschlange eingefügt wird, sodass er später von dort aus untersucht wird).

Schauen wir uns ein Beispiel an. Wir werden diesen Graphen durchqueren:

Wir werden den Graphen nach diesen Regeln durchqueren:

• Wir fangen bei der Quelle an.
• Kein Knoten wird zweimal besucht.
• Die Knoten, die wir noch nicht besucht haben, werden weiß dargestellt.
• Der Knoten, den wir besucht haben, aber nicht alle untergeordneten Knoten besucht haben, wird grau dargestellt.
• Vollständig durchlaufene Knoten werden schwarz gefärbt.

Schauen wir uns das Schritt für Schritt an:

Wir können ein wichtiges Stichwort sehen. Das ist backedge . Du kannst sehen. 5-1 heißt Backedge. Das liegt daran, dass wir mit Knoten-1 noch nicht fertig sind. Wenn Sie von einem anderen Knoten zu Knoten-1 wechseln, bedeutet dies, dass sich im Diagramm ein Zyklus befindet. Wenn wir in DFS von einem grauen Knoten zu einem anderen wechseln können, können wir sicher sein, dass der Graph einen Zyklus hat. Dies ist eine der Möglichkeiten, den Zyklus in einer Grafik zu ermitteln. Je nach Quellenknoten und der Reihenfolge der Knoten wir besuchen, können wir jede Kante in einem Zyklus als backedge erfahren. Zum Beispiel: Wenn wir zuerst von 1 auf 5 gegangen wären, hätten wir 2 : 1 als Backedge herausgefunden.

Die Kante, die wir nehmen, um vom grauen Knoten zum weißen Knoten zu gelangen, wird als Baumrand bezeichnet . Wenn wir nur den Rand des Baumes beibehalten und andere entfernen, erhalten wir den DFS-Baum .

Wenn wir in einem ungerichteten Diagramm einen bereits besuchten Knoten besuchen können, muss dies ein Backedge sein . Bei gerichteten Graphen müssen wir jedoch die Farben überprüfen. Wenn und nur dann, wenn wir von einem grauen Knoten zu einem anderen grauen Knoten wechseln können, spricht man von einem Backedge .

In DFS können wir auch Zeitstempel für jeden Knoten aufbewahren, die auf viele Arten verwendet werden können (z. B. topologische Sortierung).

1. Wenn ein Knoten v von Weiß zu Grau geändert wird, wird die Zeit in d [v] aufgezeichnet.
2. Wenn ein Knoten v von grau nach schwarz geändert wird, wird die Zeit in f [v] aufgezeichnet.

Hier bedeutet d [] Entdeckungszeit und f [] Endzeit . Unser Pesudo-Code wird folgendermaßen aussehen:

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

Komplexität:

Alle Knoten und Kanten werden einmal besucht. Die Komplexität von DFS ist also O (V + E) , wobei V die Anzahl der Knoten und E die Anzahl der Kanten bezeichnet.

Anwendungen von Depth First Search:

• Den kürzesten Weg aller Paare in einem ungerichteten Graphen finden.
• Erfassungszyklus in einer Grafik.
• Wegfindung.
• Topologische Sortierung
• Testen, ob ein Diagramm zweiteilig ist.
• Suche nach einer stark verbundenen Komponente.
• Rätsel lösen mit einer Lösung.