Breitensuche (BFS)
Zuletzt aktualisiert
Die Breitensuche erkundet einen Graphen Ebene für Ebene. Ausgehend von einem Quellknoten besucht sie zuerst alle seine direkten Nachbarn, dann alle noch nicht besuchten Nachbarn davon und so weiter - sie breitet sich in Ringen wachsender Distanz nach außen aus. Drücke oben auf Abspielen, um zu sehen, wie sie sich vom Startknoten aus Ebene für Ebene ausbreitet.
BFS verwendet eine First-in-First-out-Warteschlange, die die Reihenfolge Ebene für Ebene erzwingt. Da sie Knoten in der Reihenfolge der Sprungdistanz erreicht, findet BFS in einem ungewichteten Graphen den kürzesten Weg (die wenigsten Kanten). Sie besucht jeden Knoten und jede Kante einmal und läuft daher in O(V + E) Zeit.
Zeit- und Speicherkomplexität
| Maß | Komplexität | Anmerkungen |
|---|---|---|
| Zeit | O(V + E) | Jeder Knoten und jede Kante wird einmal besucht |
| Speicher | O(V) | Warteschlange + Besucht-Menge, im schlimmsten Fall alle Knoten |
| Durchlauf | Ebene für Ebene | Nächstgelegene Knoten zuerst, in Ringen |
| Kürzester Weg | Ja (ungewichtet) | Erreicht jeden Knoten über die wenigsten Kanten |
Schritt für Schritt
| Schritt | Was passiert |
|---|---|
| 1 | Füge den Quellknoten in die Warteschlange ein. |
| 2 | Entnimm den vordersten Knoten und markiere ihn als besucht. |
| 3 | Betrachte jeden seiner Nachbarn. |
| 4 | Füge jeden Nachbarn ein, der nicht bereits besucht oder in der Warteschlange ist. |
| 5 | Wiederhole, bis die Warteschlange leer ist. |
Durchgerechnetes Beispiel
Durchlauf dieses Graphen ab Knoten 0, wobei 0-1, 0-2, 1-3, 2-3, 2-4 Kanten sind:
| Schritt | Besucht | Warteschlange (Front) |
|---|---|---|
| Start | {} | [0] |
Entnimm 0 | {0} | [1, 2] |
Entnimm 1 | {0, 1} | [2, 3] |
Entnimm 2 | {0, 1, 2} | [3, 4] |
Entnimm 3 | {0, 1, 2, 3} | [4] |
Entnimm 4 | {0, 1, 2, 3, 4} | [] (fertig) |
Wann BFS verwenden
| Verwende es, wenn | Vermeide es, wenn |
|---|---|
| Du den kürzesten Weg in einem ungewichteten Graphen brauchst | Kanten Gewichte haben - verwende stattdessen Dijkstra |
| Das Ziel wahrscheinlich nahe an der Quelle liegt | Der Graph sehr breit ist - die Warteschlange kann eine riesige Front halten |
| Du einen Graphen in Ebenenreihenfolge erkunden willst | Du nur irgendeinen Knoten erreichen musst, wo DFS weniger Speicher braucht |
| Du Zusammenhangskomponenten oder eine Route mit minimalen Sprüngen suchst | Du topologische Sortierung oder Zyklenerkennung brauchst - DFS passt besser |
Breadth-First Search-Code
Eine saubere, lauffähige Breadth-First Search-Implementierung in Python, JavaScript, Java, C++, C. Wähle eine Sprache, kopiere den Code oder öffne ihn vorgeladen im Coddy-Playground.
Breadth-First Search-Code in Python
1from collections import deque2
3
4def bfs(graph, start):5 visited = {start}6 queue = deque([start])7 order = []8 while queue:9 node = queue.popleft()10 order.append(node)11 for neighbor in graph[node]:12 if neighbor not in visited:13 visited.add(neighbor) # mark on enqueue, not dequeue14 queue.append(neighbor)15 return order16
17
18graph = {19 "A": ["B", "C"],20 "B": ["D", "E"],21 "C": ["F"],22 "D": [],23 "E": ["F"],24 "F": [],25}26
27print("BFS order:", " -> ".join(bfs(graph, "A")))Breadth-First Search-Code in JavaScript
1const graph = {2 A: ["B", "C"],3 B: ["D", "E"],4 C: ["F"],5 D: [],6 E: ["F"],7 F: [],8};9
10function bfs(start) {11 const visited = new Set([start]);12 const queue = [start];13 const order = [];14 while (queue.length > 0) {15 const node = queue.shift(); // Dequeue the oldest node16 order.push(node);17 for (const next of graph[node]) {18 if (!visited.has(next)) {19 visited.add(next);20 queue.push(next);21 }22 }23 }24 return order;25}26
27console.log("BFS from A:", bfs("A").join(" -> "));Breadth-First Search-Code in Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 List<List<Integer>> adj = List.of(8 List.of(1, 2), // neighbors of 09 List.of(0, 3, 4), // neighbors of 110 List.of(0, 5),11 List.of(1),12 List.of(1, 5),13 List.of(2, 4)14 );15 boolean[] visited = new boolean[adj.size()];16 Queue<Integer> queue = new ArrayDeque<>();17 visited[0] = true;18 queue.add(0);19
20 StringBuilder order = new StringBuilder("BFS from 0:");21 while (!queue.isEmpty()) {22 int node = queue.poll();23 order.append(" ").append(node);24 // Mark neighbors when enqueued so nothing enters twice25 for (int next : adj.get(node)) {26 if (!visited[next]) {27 visited[next] = true;28 queue.add(next);29 }30 }31 }32 System.out.println(order);33 }34}Breadth-First Search-Code in C++
1#include <iostream>2#include <queue>3#include <vector>4
5void bfs(int start, const std::vector<std::vector<int>>& adj) {6 std::vector<bool> visited(adj.size(), false);7 std::queue<int> frontier;8 visited[start] = true;9 frontier.push(start);10 // Visit nodes level by level11 while (!frontier.empty()) {12 int node = frontier.front();13 frontier.pop();14 std::cout << node << " ";15 for (int next : adj[node]) {16 if (!visited[next]) {17 visited[next] = true;18 frontier.push(next);19 }20 }21 }22}23
24int main() {25 // 6-node undirected graph as an adjacency list26 std::vector<std::vector<int>> adj = {27 {1, 2}, // 028 {0, 3, 4}, // 129 {0, 5}, // 230 {1}, // 331 {1, 5}, // 432 {2, 4}, // 533 };34 std::cout << "BFS from node 0: ";35 bfs(0, adj);36 std::cout << "\n";37 return 0;38}Breadth-First Search-Code in C
1#include <stdbool.h>2#include <stdio.h>3
4#define N 65
6void bfs(int start, const int adj[N][N]) {7 bool visited[N] = {false};8 int queue[N]; // fixed-size queue: head chases tail9 int head = 0, tail = 0;10 visited[start] = true;11 queue[tail++] = start;12 // Visit nodes level by level13 while (head < tail) {14 int node = queue[head++];15 printf("%d ", node);16 for (int next = 0; next < N; next++) {17 if (adj[node][next] && !visited[next]) {18 visited[next] = true;19 queue[tail++] = next;20 }21 }22 }23}24
25int main(void) {26 // 6-node undirected graph as an adjacency matrix27 int adj[N][N] = {28 {0, 1, 1, 0, 0, 0},29 {1, 0, 0, 1, 1, 0},30 {1, 0, 0, 0, 0, 1},31 {0, 1, 0, 0, 0, 0},32 {0, 1, 0, 0, 0, 1},33 {0, 0, 1, 0, 1, 0},34 };35 printf("BFS from node 0: ");36 bfs(0, adj);37 printf("\n");38 return 0;39}Breitensuche FAQ
Wie ist die Zeitkomplexität von BFS?
O(V + E) Zeit, wobei V die Anzahl der Knoten und E die der Kanten ist, da es jeden Knoten einmal besucht und jede Kante einmal betrachtet. Es benötigt O(V) Speicher für die Warteschlange und die Besucht-Menge.Findet BFS den kürzesten Weg?
Ja, in einem ungewichteten Graphen. Da BFS die Knoten in der Reihenfolge der Sprungdistanz von der Quelle erreicht, erfolgt das erste Erreichen eines Knotens über einen Weg mit den wenigsten Kanten. Für gewichtete Graphen brauchst du stattdessen den Algorithmus von Dijkstra.
Was ist der Unterschied zwischen BFS und DFS?
BFS verwendet eine Warteschlange und erkundet Ebene für Ebene (die nächsten zuerst), während DFS einen Stapel verwendet und entlang eines Zweigs in die Tiefe geht, bevor es zurückkehrt. BFS findet die kürzesten ungewichteten Wege; DFS braucht bei breiten Graphen weniger Speicher und eignet sich für Zyklenerkennung und topologische Sortierung.
Wann sollte ich BFS statt des Algorithmus von Dijkstra verwenden?
O(V + E) Zeit ohne Prioritätswarteschlange. Der Algorithmus von Dijkstra ist nötig, wenn Kanten unterschiedliche Gewichte tragen; reines BFS auf einem gewichteten Graphen liefert den Weg mit den wenigsten Sprüngen, nicht den mit den geringsten Kosten.Warum braucht BFS eine Besucht-Menge?
Graphen können Zyklen enthalten, sodass BFS ohne eine Besucht-Menge denselben Knoten wiederholt einreihen und endlos schleifen würde. Einen Knoten beim ersten Einreihen zu markieren (nicht beim Entnehmen) verhindert außerdem, dass derselbe Knoten von verschiedenen Nachbarn zweimal in die Warteschlange gelegt wird.
Soll ich einen Knoten beim Einreihen oder beim Entnehmen als besucht markieren?
Markiere ihn beim Einreihen. Wenn du bis zum Entnehmen wartest, kann ein Knoten vor seiner Verarbeitung von verschiedenen Nachbarn mehrfach in die Warteschlange gelegt werden, was Speicher und Zeit verschwendet. Das Markieren beim Einreihen garantiert, dass jeder Knoten genau einmal in die Warteschlange gelangt.
Verwandte Ressourcen
Mehr Visualisierungen
