Veröffentlicht · wird verbessert
Algorithm
Graphtraversierung besucht per BFS oder DFS alle erreichbaren Knoten: Basis für ungewichtete kürzeste Wege, Komponenten, Zyklen und topologische Sortierung.
Graphtraversierung bezeichnet das systematische Besuchen aller Knoten, die von einem Startknoten aus über Kanten erreichbar sind, und zwar jeden genau einmal. Die beiden grundlegenden Verfahren sind die Breitensuche (BFS), die mit einer Warteschlange Schicht für Schicht nach außen wächst, und die Tiefensuche (DFS), die mit einem Stack oder Rekursion einem Pfad so weit wie möglich folgt und dann zurückgeht. Graphen werden meist als Adjazenzliste oder Adjazenzmatrix gespeichert; auch zweidimensionale Gitter wie Labyrinthe sind Graphen, wenn man jede Zelle als Knoten auffasst.
Straßennetze, soziale Netzwerke, Aufgabenabhängigkeiten und Weblinks sind Graphen. BFS findet kürzeste Wege, wenn alle Kanten gleich viel kosten, während DFS die Basis für Zusammenhangskomponenten, Zykluserkennung und topologische Sortierung bildet. Build-Werkzeuge, die ihre Aufgaben ordnen, Garbage Collectors, die erreichbare Objekte bestimmen, und das Füllwerkzeug in Bildbearbeitungsprogrammen beruhen auf Traversierung. In technischen Vorstellungsgesprächen gehört das Thema zu den häufigsten.
Am besten zeichnet man zuerst einen kleinen Graphen und verfolgt von Hand, wie sich die Warteschlange der BFS und der Aufrufstack der DFS verändern. Danach implementiert man beide selbst und achtet darauf, wann Knoten als besucht markiert und wie Abstände und Vorgänger gespeichert werden. Anschließend folgen kürzeste Wege im Gitter, das Zählen von Komponenten und die topologische Sortierung mit dem Algorithmus von Kahn.
Adjazenzlisten brauchen O(V + E) Speicher und passen zu dünnen Graphen; Adjazenzmatrizen prüfen Kanten in O(1), brauchen aber O(V^2) Speicher.
Eine Warteschlange besucht nahe Knoten zuerst, daher ist in ungewichteten Graphen der erste gefundene Abstand der kürzeste.
Rekursion oder ein Stack gehen in die Tiefe und kehren zurück – die Basis für Komponenten, Zykluserkennung und Backtracking.
In einem gerichteten azyklischen Graphen liefern Kahns Algorithmus oder die umgekehrte DFS-Endreihenfolge eine abhängigkeitstreue Reihenfolge.
Das Programm baut einen ungerichteten Graphen mit sechs Knoten als Adjazenzliste in einem Dictionary auf und gibt dann mit einer deque-basierten BFS die kleinste Kantenzahl von A zu jedem Knoten sowie mit einer rekursiven DFS die Besuchsreihenfolge aus. Beide Funktionen merken sich besuchte Knoten, damit keiner doppelt verarbeitet wird.
graph_traversal.py
from collections import deque
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}
def bfs(start):
"""Shortest number of edges from start to every reachable vertex."""
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return dist
def dfs(start):
"""Vertices in depth-first visiting order."""
order, seen = [], set()
def visit(node):
seen.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in seen:
visit(nxt)
visit(start)
return order
print(bfs("A")) # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}
print(dfs("A")) # ['A', 'B', 'D', 'C', 'E', 'F']
python graph_traversal.pySechs Kapitel führen dich von der Installation bis zu den Kernkonzepten von Graphtraversierung.
Stelle Fragen, teile Erfahrungen und tausche Meinungen zu Graphtraversierung aus.
Noch keine Diskussionen. Starte die erste.
0 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.