Breitensuche

Geschrieben von Daniel Graf.

Der Unterschied zwischen der Tiefensuche, welche wir im vorhergehenden Tutorial kennengelernt haben, und der Breitensuche, die wir jetzt anschauen werden, ist ein kleiner aber feiner. Abgekürzt wird die Breitensuche oft einfach mit BFS (für das Englische breadth first search).

Problembeschreibung

Wie wir gesehen haben, erlaubt uns die Tiefensuche, die Zusammenhangskomponenten eines Graphen zu bestimmen oder ihn mit zwei Farben zu färben. Was wir aber bisher noch nicht können, ist das Finden von kürzesten Wegen zwischen zwei Knoten. Die Breitensuche wird uns dies ermöglichen.

Standardalgorithmus

Breitensuche - Woher kommt der Name?

In der Tiefensuche stürzten wir uns Hals über Kopf in die Tiefe des Graphen. Wir schlugen einfach mal eine willkürliche Richtung ein und gingen so lange weiter bis wir umkehren mussten, weil wir nichts Neues mehr entdecken konnten. Erst dann schauten wir uns nach möglichen alternativen Abzweigungen um.

Die Breitensuche geht nun - wie der Name suggeriert - zuerst in die Breite statt in die Tiefe. Wir wollen zuerst alles erkunden, was unmittelbar zum Startpunkt benachbart ist. Erst danach schauen wir uns Knoten mit Distanz 2 an, also die Nachbarn der Nachbarn. Und erst wenn wir alle diese Nachbarn zweiten Grades besucht haben, dann erst beginnen wir mit den Nachbarn der Nachbarn der Nachbarn. Und so weiter.

Algorithmus: Breitensuche

Diese Idee lässt sich am einfachsten mit Hilfe einer Warteschlange (Englisch queue) implementieren. Darin merken wir uns alle Knoten, die wir entdeckt haben, deren Nachbarn wir uns aber noch anschauen wollen.

Bei der Tiefensuche erfolgten diese zwei Schritte jeweils unmittelbar hintereinander, also sobald wir einen Knoten entdeckt haben, haben wir auch gleich damit begonnen seine Nachbarn anzuschauen. Das hat uns erlaubt, die Tiefensuche mittels Rekursion zu implementieren. Nun wollen wir aber für die Breitensuche, dass wir zuerst alle Nachbarn ersten Grades anschauen, bevor wir den ersten Nachbarn zweiten Grades anschauen. Die Warteschlange simuliert nun dieses “Hinten-Anstellen-und-Warten” der neu entdeckten Knoten. In C++ kann das dann etwa so aussehen:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Wir nehmen wieder an, dass E eine nullbasierte Adjazenzliste darstellt.
vector<vector<int>> E;
vector<int> visited;

void bfs(int start) {
    queue<int> Q; // Die Warteschlange für die neu entdeckten Knoten.
    Q.push(start);
    while(!Q.empty()) {
        int v = Q.front();
        Q.pop();
        // Wir sind in Knoten v und erkunden die Nachbarschaft.
        for(int e = 0; e < E[v].size(); e++) {
            int w = E[v][e];
            // Nun prüfen wir, ob der Nachbar w noch unbesucht ist.
            if(!visited[w]) {
                visited[w] = true;
                // Anstelle des rekursiven Aufruf der DFS,
                // fügen wir w nun lediglich in die Schlange ein.
                Q.push(w);
            }
        }
    }
}

int main() {
    // Graph einlesen, wie zuvor.
    int n, m;
    // ...
    // Nun können wir die Breitensuche starten
    int start = 0;
    visited = vector<int>(n, false); // Zu Beginn haben wir noch nichts besucht.
    visited[start] = true;
    bfs(start);
    // In visited[] können wir nun wiederum ablesen, ob
    // ein bestimmter Knoten erreicht werden kann.
}

Bild 1 zeigt dir an einem Beispiel wie sich die Besuchsreihenfolge der Knoten in einer Breitensuche und einer Tiefensuche unterscheiden können.

Bild 1: Die Breitensuche (links) und Tiefensuche (rechts) auf dem selben Graphen. Die Zahlen geben die Entdeckungsreihenfolge der Knoten an und die Pfeile bezeichnen die Kanten entlang welcher die Knoten entdeckt wurden.

Kürzeste Wege

Für ungerichtete, ungewichtete Graphen erlaubt uns die Breitensuche, die Länge des kürzesten Weges zwischen dem Startpunkt und jedem beliebigen anderen Knoten zu bestimmen. Die Länge eines Pfades messen wir in der Anzahl Kanten, denen wir entlanggehen. Ungewichtet heisst hier also, dass jede Kante als gleich lang gezählt wird. Falls die Kanten unterschiedliche Länge haben, genügt die Breitensuche nicht mehr, um den kürzesten Weg zu berechnen. Der Algorithmus von Dijkstra, welcher dir in einer anderen Aufgabe erklärt wird, löst aber genau dieses Problem. Aber wie berechnen wir nun die ungewichtete Länge des kürzesten Weges von a nach b mit Hilfe der Breitensuche?

Die Erkundungsreihenfolge der BFS hat die schöne Eigenschaft, dass wir die Knoten in aufsteigender Distanz zum Startknoten besuchen. Das heisst z. B., dass wir alle Knoten mit Distanz 5 unmittelbar nach den Knoten mit Distanz 4 und umittelbar vor den Knoten mit Distanz 6 besuchen. Wenn immer wir also einen neuen Knoten entdecken, können wir dessen Distanz zum Start direkt bestimmen, nämlich als die Distanz zum aktuellen Knoten plus 1.

In der Implementierung von oben können wir dies einbauen, indem wir zum Beispiel einen Vektor dist hinzufügen, den wir für jeden Knoten mit unendlich initialisieren (oder einfach einer fixen, sehr grossen Zahl) und dann dist[start] auf Null setzen. Die Distanz der neu entdeckten Knoten setzen wir dann hier mit einer einzigen neuen Zeile:

...
if(!visited[w]) {
    visited[w] = true;
    // Anstelle des rekursiven Aufruf der DFS,
    // fügen wir w nun lediglich in die Schlange ein.
    Q.insert(w);
    dist[w] = dist[v] + 1; // Neue Zeile!
}
...

Bild 2 zeigt nochmals denselben Graphen aber jetzt mit den Distanzangaben zwischen den Knoten und dem Start.

Bild 2: Die Distanzen nach einer Breitensuche, die beim obersten Knoten begonnen hat.

Zusammenfassung

DFS und BFS haben also einige simple aber dennoch wichtige Anwendungen: Prüfen, ob zwischen zwei Knoten ein Pfad existiert, die Anzahl der Zusammenhangskomponenten zählen, Zweifärben (diese Algorithmen funktionieren sowohl mit DFS als auch mit BFS) sowie den kürzesten Pfad zwischen zwei Knoten in einem ungewichteten Graphen finden (ganz wichtig: dieser Algorithmus geht nur mit BFS).