Breitensuche

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 w : E[v]) {
            // 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.
}

from collections import deque  # Wir benutzen deque aus collections für unsere Warteschlange.

def bfs(graph, start, visited):
    q = deque()
    q.append(start)
    visited[start] = True
    while len(q) > 0:
        v = q[0]
        q.popleft()
        # Wir sind in Knoten v und erkundien die Nachbarschaft.
        for w in graph[v]:
            # Nun prüfen wir, ob der Nachbar w noch unbesucht ist.
            if not visited[w]:
                visited[w] = True
                # Anstelle des rekursiven Aufrufs der DFS
                # fügen wir w nun lediglich in die Schlange ein.
                q.append(w)

if __name__ == '__main__':
    # Graph einlesen als nullbasierte Adjazenzliste, wie zuvor.
    # ...
    # Nun können wir die Breitensuche starten.
    start = 0
    visited = n*[False]
    bfs(graph, start, visited)
    # 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 einem anderen Artikel 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 vom Start 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!
}
...

...
if not visited[w]:
    visited[w] = True
    # Anstelle des rekursiven Aufrufs der DFS
    # fügen wir w nun lediglich in die Schlange ein.
    q.append(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.