Der Breitensuchalgorithmus (Breadth-first-search, BFS) ist ein Algorithmus, der verwendet wird, um das Problem des kürzesten Pfades in einem Graphen ohne Kantengewichte zu lösen (d.h. ein Diagramm, in dem alle Knoten den gleichen “Abstand” voneinander haben und entweder verbunden sind oder nicht). Dies bedeutet, dass bei einer Anzahl von Knoten und den Kanten zwischen ihnen der Breitensuchalgorithmus den kürzesten Weg vom angegebenen Startknoten zu allen anderen Knoten findet.

Beschreibung des Algorithmus

Das Grundprinzip des Breitensuchalgorithmus besteht darin, den aktuellen Knoten (den Startknoten am Anfang) zu nehmen und dann alle seine Nachbarn, die wir noch nicht besucht haben, zu einer Warteschlange hinzuzufügen. Fahren Sie mit dem nächsten Knoten in der Warteschlange fort (in einer Warteschlange, die der “älteste” Knoten ist). Bevor wir der Warteschlange einen Knoten hinzufügen, setzen wir seinen Abstand auf den Abstand des aktuellen Knotens plus 1 (da alle Kanten gleich gewichtet sind), wobei der Abstand zum Startknoten 0 ist. Dies wird wiederholt, bis sich keine Knoten mehr in der Warteschlange befinden (alle Knoten werden besucht).

Im Einzelnen führt dies zu den folgenden Schritten:

1. Initialisieren Sie die Entfernung zum Startknoten als 0. Die Entfernungen zu allen anderen Knoten müssen nicht initialisiert werden, da jeder Knoten genau einmal besucht wird.
2. Setzen Sie alle Knoten auf “nicht besucht”.
3. Fügen Sie den ersten Knoten zur Warteschlange hinzu und kennzeichnen Sie ihn als besucht.

4. Während sich Knoten in der Warteschlange befinden:

   1. Nehmen Sie einen Knoten aus der Warteschlange
   2. Fügen Sie für alle Knoten daneben, die wir noch nicht besucht haben, sie der Warteschlange hinzu, stellen Sie ihre Entfernung auf die Entfernung zum aktuellen Knoten plus 1 ein und legen Sie sie als “besucht” fest.

Am Ende sind die Abstände zu allen Knoten korrekt.

Beispiel des Algorithmus

Betrachten Sie das folgende Diagramm:

Die Schritte, die der Algorithmus in diesem Diagramm ausführt, wenn der Knoten 0 als Startpunkt angegeben wird, sind:

1. Besuche Knoten 0

2. Besuchte Knoten: [wahr, falsch, falsch, falsch, falsch, falsch], Entfernungen: [0, 0, 0, 0, 0, 0]

   1. Knoten 0 aus der Warteschlange entfernen …
   2. Besuchen Sie Knoten 1, setzen Sie seinen Abstand auf 1 und fügen Sie ihn der Warteschlange hinzu
   3. Besuchen Sie Knoten 2, setzen Sie seinen Abstand auf 1 und fügen Sie ihn der Warteschlange hinzu

3. Besuchte Knoten: [wahr, wahr, wahr, falsch, falsch, falsch], Entfernungen: [0, 1, 1, 0, 0, 0]

   1. Entfernen von Knoten 1 aus der Warteschlange …
   2. Besuchen Sie Knoten 3, setzen Sie seinen Abstand auf 2 und fügen Sie ihn der Warteschlange hinzu
   3. Besuchen Sie Knoten 4, stellen Sie seinen Abstand auf 2 ein und fügen Sie ihn der Warteschlange hinzu

4. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, falsch], Entfernungen: [0, 1, 1, 2, 2, 0]

   1. Entfernen von Knoten 2 aus der Warteschlange …
   2. Keine benachbarten, nicht besuchten Knoten

5. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, falsch], Entfernungen: [0, 1, 1, 2, 2, 0]

   1. Entfernen von Knoten 3 aus der Warteschlange …
   2. Besuchen Sie Knoten 5, stellen Sie seinen Abstand auf 3 ein und fügen Sie ihn der Warteschlange hinzu

6. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, wahr], Entfernungen: [0, 1, 1, 2, 2, 3]

   1. Entfernen von Knoten 4 aus der Warteschlange …
   2. Keine benachbarten, nicht besuchten Knoten

7. Besuchte Knoten: [wahr, wahr, wahr, wahr, wahr, wahr], Entfernungen: [0, 1, 1, 2, 2, 3]

   1. Entfernen von Knoten 5 aus der Warteschlange …
8. Keine Knoten mehr in der Warteschlange. Endabstände: [0, 1, 1, 2, 2, 3]

Laufzeitkomplexität des Algorithmus

Die Laufzeitkomplexität der Breitensuche beträgt O(|E| + |V|) (|V| = Anzahl der Knoten, |E| = Anzahl der Kanten), wenn Adjazenzlisten verwendet werden. Wenn wir einfach alle Knoten durchsuchen, um in jedem Schritt verbundene Knoten zu finden, und mithilfe einer Matrix nachsehen, ob zwei Knoten benachbart sind, steigt die Laufzeitkomplexität auf O(|V|^2).

Abhängig vom Diagramm spielt dies möglicherweise keine Rolle, da die Anzahl der Kanten bis zu |V|^2 betragen kann, wenn alle Knoten miteinander verbunden sind.

Speicherplatzkomplexität des Algorithmus

Die Speicherplatzkomplexität der Breitensuche hängt auch davon ab, wie sie implementiert ist, und entspricht der Laufzeitkomplexität.