Graph-Traversierung

Die Graph-Traversierung besucht systematisch die Knoten und Kanten eines Graphen; die Breitensuche (BFS) erkundet Ebene für Ebene, während die Tiefensuche (DFS) so tief wie möglich erkundet, bevor sie zurückverfolgt, und zusammen bilden sie die Grundlage der meisten Graph-Algorithmen.

Definition

Graph-Traversierung ist der Prozess des systematischen Besuchens jedes Knotens (und Untersuchens jeder Kante) eines Graphen; die Breitensuche besucht Knoten in der Reihenfolge ihrer Entfernung von einer Quelle, und die Tiefensuche folgt jedem Pfad bis zu seinem Ende, bevor sie zurückverfolgt.

Scope

Dieses Thema behandelt die beiden grundlegenden Graphensuchstrategien, die Breitensuche (BFS) und die Tiefensuche (DFS), ihre Warteschlangen- und Stack-basierten Implementierungen sowie die strukturellen Informationen, die sie aufdecken – Erreichbarkeit, zusammenhängende Komponenten, kürzeste Pfade in ungewichteten Graphen, topologische Sortierung, Zyklenerkennung und stark zusammenhängende Komponenten. Ausgenommen sind gewichtete kürzeste Pfade und Flussprobleme, die auf der Traversierung aufbauen, aber separat behandelt werden.

Core questions

• Wie unterscheiden sich BFS und DFS in der Reihenfolge, in der sie Knoten besuchen, und was deckt jede auf?
• Wie berechnet BFS die kürzesten Pfade in einem ungewichteten Graphen?
• Wie ermöglicht DFS topologische Sortierung, Zyklenerkennung und Komponentenzerlegung?
• Warum laufen beide Traversierungen in linearer Zeit bezüglich der Anzahl der Knoten plus Kanten?
• Wie werden besuchte Markierungen und Frontier-Strukturen verwendet, um das erneute Besuchen von Knoten zu vermeiden?

Key concepts

• Breitensuche (BFS)
• Tiefensuche (DFS)
• Menge der besuchten Knoten
• Warteschlangen- und Stack-Frontiers
• zusammenhängende Komponenten
• topologische Sortierung
• Zyklenerkennung
• stark zusammenhängende Komponenten

Key theories

Breitensuche und ungewichtete kürzeste Pfade

BFS besucht Knoten in nicht abnehmender Reihenfolge der Entfernung von der Quelle unter Verwendung einer Warteschlange, wodurch die minimale Anzahl von Kanten von der Quelle zu jedem erreichbaren Knoten in linearer Zeit berechnet wird.

Tiefensuche und lineare Graph-Algorithmen

DFS liefert mit ihren Entdeckungs- und Abschlusszeiten sowie der Kantenklassifizierung lineare Algorithmen für die topologische Sortierung, Zyklenerkennung und das Finden stark zusammenhängender Komponenten, wie von Tarjan systematisiert.

Clinical relevance

Traversierungsalgorithmen sind allgegenwärtig: BFS findet die kürzesten Hop-Zahlen in ungewichteten Netzwerken und liegt Webcrawlern sowie Peer-to-Peer-Broadcast zugrunde; DFS treibt die Abhängigkeitsauflösung und Build-Systeme mittels topologischer Sortierung, Deadlock-Erkennung, Labyrinth- und Rätsellösung sowie Komponentenanalyse in sozialen und biologischen Netzwerken an.

History

Die Breitensuche geht auf Moores Arbeit von 1959 zur Labyrinth-Routung und verwandte unabhängige Bemühungen zurück. Die Tiefensuche wurde 1972 von Robert Tarjan auf eine rigorose algorithmische Grundlage gestellt, dessen lineare Algorithmen für stark zusammenhängende Komponenten und Bikonnetivität DFS als leistungsstarkes allgemeines Werkzeug demonstrierten.

Key figures

• Robert Tarjan
• Edward F. Moore
• John Hopcroft

Seminal works

• tarjan1972
• cormen2009

Frequently asked questions

Wann sollte ich BFS anstelle von DFS verwenden?

Verwenden Sie BFS, wenn Sie den kürzesten Pfad in Bezug auf die Anzahl der Kanten benötigen oder den Graphen in der Reihenfolge der Entfernung von einer Quelle erkunden möchten. Verwenden Sie DFS für Probleme, die die Struktur betreffen – topologische Sortierung, Zyklenerkennung, zusammenhängende oder stark zusammenhängende Komponenten – wo ein tiefes Erkunden und Zurückverfolgen natürlich ist.

Warum sind BFS und DFS beide linear in der Laufzeit?

Jeder Knoten wird einmal als besucht markiert und verarbeitet, und jede Kante wird eine konstante Anzahl von Malen untersucht, sodass der Gesamtaufwand proportional zur Anzahl der Knoten plus der Anzahl der Kanten ist, geschrieben als O(V + E).