BFS erkundet einen Graphen Ebene für Ebene und besucht alle Nachbarn eines Knotens, bevor es tiefer geht. Sie verwendet eine Queue und findet den kürzesten Pfad (wenigste Kanten) in ungewichteten Graphen.
Beginnen Sie bei einer Quelle, fügen Sie sie zur Queue hinzu, entfernen Sie dann wiederholt einen Knoten aus der Queue, besuchen Sie seine unbesuchten Nachbarn und fügen Sie sie zur Queue hinzu. Eine -Menge verhindert erneute Besuche.
visitedfrom collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # FIFO: explore nearest first
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A') # -> ['A', 'B', 'C', 'D']
Verwenden Sie BFS für kürzeste Pfade in ungewichteten Graphen, Level-Order-Traversierung und zum Finden verbundener Komponenten. Sie verbraucht mehr Speicher als DFS (eine ganze Grenze auf einmal). Verfolgen Sie immer visited, oder Sie können in eine Endlosschleife bei Zyklen geraten.
BFS ist der Algorithmus für kürzeste Pfade, wenn jede Kante gleich zählt — Routing, Web-Crawling, Grade der Trennung in sozialen Netzwerken.
Ihre Queue-basierte, Ebene-für-Ebene-Struktur ist ein grundlegendes Durchlaufmuster.
BFS vs. DFS zu kennen ermöglicht es Ihnen, das richtige Werkzeug für Erreichbarkeits-, Pfad- und Sortierprobleme zu wählen.