Datenstruktur - Breite erste Durchquerung
Der BFS-Algorithmus (Breadth First Search) durchläuft ein Diagramm in einer Bewegung in der Breite und verwendet eine Warteschlange, um sich daran zu erinnern, den nächsten Scheitelpunkt zum Starten einer Suche zu erhalten, wenn in einer Iteration eine Sackgasse auftritt.
Wie im obigen Beispiel durchläuft der BFS-Algorithmus zuerst von A nach B nach E nach F, dann nach C und zuletzt nach D. Er verwendet die folgenden Regeln.
Rule 1- Besuchen Sie den angrenzenden nicht besuchten Scheitelpunkt. Markieren Sie es als besucht. Zeigen Sie es an. Fügen Sie es in eine Warteschlange ein.
Rule 2 - Wenn kein benachbarter Scheitelpunkt gefunden wird, entfernen Sie den ersten Scheitelpunkt aus der Warteschlange.
Rule 3 - Wiederholen Sie Regel 1 und Regel 2, bis die Warteschlange leer ist.
| Schritt | Durchquerung | Beschreibung |
|---|---|---|
| 1 |
|
Initialisieren Sie die Warteschlange. |
| 2 |
|
Wir beginnen mit einem Besuch S (Startknoten) und markieren Sie ihn als besucht. |
| 3 |
|
Wir sehen dann einen nicht besuchten Nachbarknoten von S. In diesem Beispiel haben wir drei Knoten, aber wir wählen sie alphabetisch ausA, markieren Sie es als besucht und stellen Sie es in die Warteschlange. |
| 4 |
|
Als nächstes wird der nicht besuchte Nachbarknoten von S ist B. Wir markieren es als besucht und stellen es in die Warteschlange. |
| 5 |
|
Als nächstes wird der nicht besuchte Nachbarknoten von S ist C. Wir markieren es als besucht und stellen es in die Warteschlange. |
| 6 |
|
Jetzt, Sbleibt ohne nicht besuchte benachbarte Knoten. Also stellen wir uns in die Warteschlange und findenA. |
| 7 |
|
Von A wir haben Dals nicht besuchter Nachbarknoten. Wir markieren es als besucht und stellen es in die Warteschlange. |
Zu diesem Zeitpunkt haben wir keine nicht markierten (nicht besuchten) Knoten mehr. Gemäß dem Algorithmus werden wir jedoch weiterhin aus der Warteschlange entfernt, um alle nicht besuchten Knoten zu erhalten. Wenn die Warteschlange geleert wird, ist das Programm beendet.
Die Implementierung dieses Algorithmus in der Programmiersprache C ist hier zu sehen .