Einführung in den BFS-Algorithmus
Um effizient auf die Daten zuzugreifen und sie zu verwalten, können sie in einem speziellen Format gespeichert und organisiert werden, das als Datenstruktur bezeichnet wird. Es gibt viele Datenstrukturen wie Stapel, Array, verknüpfte Liste, Warteschlangen, Bäume und Diagramme usw. In linearen Datenstrukturen wie Stapel, Array, verknüpfte Liste und Warteschlange sind die Daten in linearer Reihenfolge Bei linearen Datenstrukturen wie Bäumen und Grafiken sind die Daten hierarchisch und nicht in einer Sequenz angeordnet. Der Graph ist eine nichtlineare Datenstruktur mit Knoten und Kanten. Knoten in Graph können auch als Eckpunkte bezeichnet werden, deren Anzahl begrenzt ist, und Kanten sind die Verbindungslinien zwischen zwei beliebigen Knoten.
In der obigen Grafik können Scheitelpunkte als V = (A, B, C, D, E) dargestellt und Kanten als definiert werden
E = (AB, AC, CD, BE)
Was ist der BFS-Algorithmus?
Es gibt im Allgemeinen zwei Algorithmen, die zum Durchlaufen eines Graphen verwendet werden. Dies sind BFS- (Breadth-First Search) und DFS-Algorithmen (Depth First Search). Beim Durchlaufen des Diagramms wird genau einmal jeder Scheitelpunkt oder Knoten und jede Kante in einer genau definierten Reihenfolge aufgerufen. Außerdem ist es sehr wichtig, die besuchten Scheitelpunkte zu verfolgen, damit derselbe Scheitelpunkt nicht zweimal durchlaufen wird. Beim Breath First Search-Algorithmus beginnt die Überquerung bei einem ausgewählten Knoten oder Quellknoten, und die Überquerung wird über die Knoten fortgesetzt, die direkt mit dem Quellknoten verbunden sind. Einfacher ausgedrückt, sollte man im BFS-Algorithmus zuerst die aktuelle Ebene horizontal verschieben und überqueren, danach sollte die Verschiebung zur nächsten Ebene erfolgen.
Wie funktioniert der BFS-Algorithmus?
Nehmen wir das folgende Diagramm als Beispiel.
Die wichtige Aufgabe besteht darin, den kürzesten Pfad in einer Grafik zu finden, während die Knoten überquert werden. Beim Durchlaufen eines Graphen wechselt der Scheitelpunkt vom unentdeckten in den entdeckten Zustand und wird schließlich vollständig entdeckt. Es ist anzumerken, dass es möglich ist, irgendwann beim Durchlaufen eines Graphen hängen zu bleiben und ein Knoten zweimal besucht werden kann. Wir können also eine Methode zum Markieren der Knoten anwenden, nachdem der Status "Unentdeckt" in "Vollständig entdeckt" geändert wurde.
In der folgenden Abbildung ist zu sehen, dass die Knoten in den Diagrammen markiert werden können, wenn sie vollständig entdeckt werden, indem sie mit Schwarz markiert werden. Wir können am Quellknoten beginnen und während der Durchlauf durch jeden Knoten fortschreitet, können sie markiert werden, um identifiziert zu werden.
Die Überquerung beginnt an einem Scheitelpunkt und verläuft dann zu den ausgehenden Kanten. Wenn eine Kante zu einem unentdeckten Scheitelpunkt führt, wird sie als entdeckt markiert. Wenn eine Kante jedoch zu einem vollständig entdeckten oder entdeckten Scheitelpunkt führt, wird sie ignoriert.
Bei einem gerichteten Graphen wird jede Kante einmal besucht, und bei einem ungerichteten Graphen wird sie zweimal besucht, dh einmal, während jeder Knoten besucht wird. Der zu verwendende Algorithmus wird auf der Grundlage der Speicherung der erkannten Scheitelpunkte festgelegt. Im BFS-Algorithmus wird die Warteschlange verwendet, in der der älteste Scheitelpunkt zuerst erkannt wird und sich dann vom Startscheitelpunkt aus durch die Ebenen ausbreitet.
Schritte werden für einen BFS-Algorithmus ausgeführt
Die folgenden Schritte werden für einen BFS-Algorithmus ausgeführt.
- Beginnen wir in einem gegebenen Diagramm mit einem Scheitelpunkt, dh im obigen Diagramm ist es der Knoten 0. Die Ebene, in der dieser Scheitelpunkt vorhanden ist, kann als Schicht 0 bezeichnet werden.
- Der nächste Schritt besteht darin, alle anderen Scheitelpunkte zu finden, die neben dem Startscheitelpunkt, dh dem Knoten 0, liegen oder von diesem aus unmittelbar zugänglich sind. Dann können wir diese benachbarten Scheitelpunkte als auf Ebene 1 vorhanden markieren.
- Es ist möglich, aufgrund einer Schleife in der Grafik zum gleichen Scheitelpunkt zu gelangen. Wir sollten also nur zu den Scheitelpunkten reisen, die in derselben Ebene vorhanden sein sollten.
- Als Nächstes wird der übergeordnete Scheitelpunkt des aktuellen Scheitelpunkts markiert, an dem wir uns befinden. Gleiches gilt für alle Vertices auf Layer 1.
- Der nächste Schritt besteht darin, alle Scheitelpunkte zu finden, die eine einzelne Kante von allen Scheitelpunkten auf Ebene 1 entfernt sind. Diese neue Gruppe von Scheitelpunkten befindet sich auf Ebene 2.
- Der obige Vorgang wird wiederholt, bis alle Knoten durchlaufen sind.
Beispiel:
Nehmen wir das folgende Diagramm als Beispiel und verstehen, wie der BFS-Algorithmus funktioniert. Im Allgemeinen wird in einem BFS-Algorithmus eine Warteschlange verwendet, um die Knoten in die Warteschlange zu stellen, während die Knoten durchlaufen werden.
In der obigen Grafik muss zuerst der Knoten 0 besucht werden, und dieser Knoten wird in die folgende Warteschlange eingereiht:
Nach dem Besuch des Knotens 0 wird der benachbarte Knoten von 0, 1 und 2 in die Warteschlange eingereiht. Die Warteschlange kann wie folgt dargestellt werden: 
Dann wird der erste Knoten in der Warteschlange, der 2 ist, besucht. Nachdem der Knoten 2 besucht wurde, kann die Warteschlange wie folgt dargestellt werden:
Nach dem Besuch des Knotens 2 wird 5 in die Warteschlange gestellt, und da es für den Knoten 5 keine nicht besuchten Nachbarknoten gibt, befindet sich 5 zwar in der Warteschlange, wird jedoch nicht zweimal besucht.
Als nächstes ist der erste Knoten in der Warteschlange 1, der besucht wird. Die benachbarten Knoten 3 und 4 stehen in der Warteschlange. Die Warteschlange wird wie folgt dargestellt
Als nächstes ist der erste Knoten in der Warteschlange 5, und für diesen Knoten gibt es keine nicht besuchten Nachbarknoten mehr. Gleiches gilt für die Knoten 3 und 4, für die es auch keine unbesuchten Nachbarknoten mehr gibt.
So werden alle Knoten durchlaufen und schließlich wird die Warteschlange leer.
Fazit
Der Breitensuchalgorithmus bietet einige große Vorteile, die es zu empfehlen gilt. Eine der vielen Anwendungen des BFS-Algorithmus ist die Berechnung des kürzesten Pfades. Es wird auch beim Networking zum Auffinden benachbarter Knoten verwendet und kann in sozialen Netzwerken, im Netzwerk-Broadcasting und in der Garbage Collection verwendet werden. Die Benutzer müssen die Anforderung und das Datenmuster verstehen, um sie für eine bessere Leistung zu verwenden.
Empfohlene Artikel
Dies war eine Anleitung zum BFS-Algorithmus. Hier diskutieren wir das Konzept, die Arbeitsweise, die Schritte und das Leistungsbeispiel des BFS-Algorithmus. Sie können auch unsere anderen Artikelvorschläge durchgehen, um mehr zu erfahren -
- Was ist ein Greedy-Algorithmus?
- Ray-Tracing-Algorithmus
- Algorithmus für digitale Signaturen
- Was ist Java Hibernate?
- Kryptographie mit digitaler Signatur
- BFS VS DFS | Top 6 Unterschiede zu Infografiken