BFS Visualisierer Online

Pseudocode

Der gesamte Algorithmus besteht aus einer Warteschlange und einer Besuchtmenge. Alles Weitere, wofür BFS bekannt ist, folgt aus der Reihenfolge, in der die Warteschlange die Knoten zurückgibt.

BFS(graph, quelle):
    besucht = {quelle}
    dist[quelle] = 0
    schlange = [quelle]

    solange die Schlange nicht leer ist:
        u = schlange.entferneErstes()
        für jeden Nachbarn v von u:
            wenn v nicht in besucht:
                besucht.hinzufügen(v)
                dist[v] = dist[u] + 1
                vorgänger[v] = u
                schlange.hängeAn(v)

Die Invariante lautet, dass die Warteschlange stets Knoten aus höchstens zwei aufeinanderfolgenden Distanzebenen enthält, in nicht fallender Reihenfolge. Genau diese Eigenschaft macht dist korrekt: Ein Knoten erhält seine Distanz beim ersten Sehen, und später kann er nicht mehr günstiger erreicht werden.

Durchgerechnetes Beispiel, Schritt für Schritt

Führe BFS von A aus auf dem Graphen, den der Visualisierer standardmäßig lädt, damit sich jeder Schritt oben im Panel mitverfolgen lässt.

Beispielgraph: Ungerichtete Kanten A-B (2), A-C (3), B-C (1) und C-D (4). BFS ignoriert die Gewichte vollständig und zählt Schritte, jede Kante zählt also eins.

1. Start. Markiere A als besucht mit dist 0 und lege es in die Warteschlange. Schlange: [A].
2. A entnehmen. A hat die Nachbarn B und C, keiner ist besucht. Beide erhalten dist 1 und Vorgänger A. Schlange: [B, C].
3. B entnehmen. B hat die Nachbarn A und C. Beide sind bereits besucht: A als Quelle, C kurz zuvor von A beansprucht. Es wird nichts hinzugefügt. Dieser Schritt zeigt, warum BFS nie erneut besucht: C über B zu erreichen kostete 2 Schritte gegenüber dem bereits eingetragenen 1. Schlange: [C].
4. C entnehmen. C hat die Nachbarn A, B und D. Nur D ist neu und erhält dist 2 und Vorgänger C. Schlange: [D].
5. D entnehmen. Der einzige Nachbar von D ist C und bereits besucht. Die Schlange leert sich und die Suche endet.

Die Enddistanzen sind A 0, B 1, C 1, D 2, und die Vorgängerzeiger ergeben den Kürzeste-Wege-Baum A zu B, A zu C und C zu D. Beachte, dass BFS D über C erreicht, obwohl die gewichteten Kosten dieses Weges 7 betragen gegenüber 3 für A zu B zu C: Optimiert wird ausschließlich die Zahl der Schritte, und genau deshalb brauchen gewichtete Graphen Dijkstra.

Komplexität und woher sie kommt

Zeit: O(V + E) · Speicher: O(V)

Jeder Knoten betritt die Warteschlange höchstens einmal, weil er beim Einfügen als besucht markiert wird und nicht erst beim Entnehmen. Das begrenzt die äußere Schleife auf V Durchläufe. Innerhalb der Schleife ist der Aufwand proportional zum Grad des aktuellen Knotens, und die Summe aller Grade beträgt 2E in einem ungerichteten Graphen, sodass das Durchmustern der Nachbarn insgesamt O(E) kostet. Der Speicher wird von Besuchtmenge, Distanzfeld und Warteschlange bestimmt, jeweils O(V). Mit einer Adjazenzmatrix kostet das Durchmustern der Nachbarn O(V) je Knoten und der gesamte Lauf verschlechtert sich auf O(V hoch 2).

Wann Breitensuche passt und wann nicht

BFS ist die richtige Voreinstellung, solange die Kanten ungewichtet sind. Sobald Gewichte auftreten oder das Ziel von Distanz auf Struktur wechselt, gewinnt etwas anderes.

Häufige Fehler

• Beim Entnehmen statt beim Einfügen als besucht markieren. Wird ein Knoten erst markiert, wenn er die Warteschlange verlässt, kann er vor seiner ersten Entnahme vielfach eingefügt werden. Bei dichten Graphen wird aus einem linearen Durchlauf ein quadratischer, und der Speicher kann ausgehen. Markiere ihn im Moment des Einfügens.
• BFS auf einem gewichteten Graphen verwenden. BFS zählt Schritte, nicht Gewicht. In einem Graphen, in dem A nach C 100 über eine Kante kostet und A nach B nach C 2 über zwei Kanten, meldet BFS den Weg mit Kosten 100 als kürzer. Greife stattdessen zu Dijkstra.
• Den Weg allein aus den Distanzen rekonstruieren. Distanzen sagen, wie weit, nicht wie herum. Speichere beim Zuweisen einer Distanz einen Vorgängerzeiger, laufe dann vom Ziel über die Vorgänger zurück und drehe das Ergebnis um.
• Rekursion statt Warteschlange. Ein rekursiver Durchlauf ist tiefenorientiert, ganz gleich wie man ihn nennt. BFS braucht eine explizite FIFO-Warteschlange; eine natürliche rekursive Formulierung gibt es nicht.

Häufig gestellte Fragen

Wofür wird die Breitensuche verwendet?

BFS findet kürzeste Wege in ungewichteten Graphen, prüft Zusammenhang und Bipartitheit und durchläuft Bäume ebenenweise. Sie ist außerdem die Suche nach augmentierenden Pfaden in Edmonds-Karp für den maximalen Fluss und trägt Kürzeste-Schritte-Anfragen in sozialen Netzen und Routingnetzen.

Wie ist die Zeitkomplexität von BFS?

O(V + E) Zeit und O(V) Speicher mit Adjazenzliste, wobei V die Zahl der Knoten und E die der Kanten ist. Mit einer Adjazenzmatrix wird daraus O(V hoch 2), weil jedes Durchmustern der Nachbarn unabhängig vom tatsächlichen Grad O(V) kostet.

Findet BFS immer den kürzesten Weg?

In ungewichteten Graphen ja, in gewichteten nein. BFS expandiert Knoten in nicht fallender Reihenfolge der Schrittzahl, sodass sie beim ersten Erreichen eines Knotens die kleinstmögliche Zahl an Kanten verwendet hat. Sobald Kanten unterschiedliche Gewichte tragen, bricht diese Garantie, weil wenigste Kanten und geringstes Gesamtgewicht nicht mehr dasselbe sind.

Was ist der Unterschied zwischen BFS und DFS?

BFS erkundet ebenenweise mit einer Warteschlange und findet kürzeste Wege in ungewichteten Graphen. DFS folgt einem Ast bis zum Ende mit Stapel oder Rekursion und legt Struktur offen: Zyklen, topologische Ordnung, starke Zusammenhangskomponenten. BFS braucht mehr Speicher bei breiten Graphen, DFS mehr bei tiefen.

Kann BFS einen Zyklus erkennen?

Ja. Erreicht BFS in einem ungerichteten Graphen einen bereits besuchten Knoten, der nicht der Vorgänger des aktuellen Knotens ist, schließt diese Kante einen Zyklus. In gerichteten Graphen passt BFS schlecht, dort sind Kahns topologische Sortierung oder eine DFS mit Kantenklassifikation üblich.