Algorithmus der Breitensuche (BFS) mit BEISPIEL
Sarah Chen
⚡ Intelligente Zusammenfassung
Die Breitensuche (BFS) ist ein Algorithmus, der einen Graphen Ebene für Ebene durchläuft und dabei alle Nachbarn eines Knotens besucht, bevor er tiefer geht. Er verwendet eine FIFO-Warteschlange und findet den kürzesten Pfad in ungewichteten Graphen ohne Endlosschleifen.
Was ist der BFS-Algorithmus (Breadth-First Search)?
Die Breitensuche (BFS) ist ein Algorithmus, der zum Durchsuchen von Daten in Graphen, Bäumen oder anderen Strukturen verwendet wird. Die Abkürzung BFS steht für Breitensuche.
Der Algorithmus besucht und markiert effizient alle wichtigen Knoten in einem Diagramm in einer genauen Breitenordnung. Dieser Algorithmus wählt einen einzelnen Knoten (Anfangs- oder Quellpunkt) in einem Diagramm aus und besucht dann alle Knoten, die an den ausgewählten Knoten angrenzen. Denken Sie daran, dass BFS diese Knoten einzeln aufruft.
Sobald der Algorithmus den Startknoten besucht und markiert hat, bewegt er sich zu den nächsten, noch nicht besuchten Knoten und analysiert diese. Nach dem Besuch werden alle Knoten markiert. Diese Iterationen werden fortgesetzt, bis alle Knoten des Graphen erfolgreich besucht und markiert wurden.
Was sind Graphdurchquerungen?
Ein Graphdurchlauf ist eine häufig verwendete Methode zum Auffinden der Scheitelpunktposition im Graphen. Es handelt sich um einen erweiterten Suchalgorithmus, der den Graphen schnell und präzise analysieren und gleichzeitig die Reihenfolge der besuchten Eckpunkte markieren kann. Dieser Prozess ermöglicht es Ihnen, jeden Knoten in einem Diagramm schnell zu besuchen, ohne in einer Endlosschleife gefangen zu sein.
Die Architektur des BFS-Algorithmus
- Auf den verschiedenen Datenebenen kann jeder Knoten als Startknoten für die Suche markiert werden. Die Breitensuche (BFS) besucht den Knoten, markiert ihn als besucht und reiht ihn in die Warteschlange ein.
- Die Breitensuche (BFS) besucht nun die nächstgelegenen, noch nicht besuchten Knoten und markiert sie. Diese Werte werden ebenfalls der Warteschlange hinzugefügt. Die Warteschlange arbeitet mit der FIFO-Modell.
- In ähnlicher Weise werden die verbleibenden nächstgelegenen und noch nicht besuchten Knoten im Graphen analysiert, markiert und der Warteschlange hinzugefügt. Diese Elemente werden nach dem Empfang aus der Warteschlange entfernt und als Ergebnis ausgegeben.
Warum brauchen wir den BFS-Algorithmus?
Es gibt zahlreiche Gründe, den BFS-Algorithmus zur Suche in Ihrem Datensatz zu verwenden. Einige der wichtigsten Aspekte, die diesen Algorithmus zur ersten Wahl machen, sind:
- BFS ist nützlich, um die Knoten in einem Diagramm zu analysieren und den kürzesten Pfad zum Durchqueren dieser Knoten zu konstruieren.
- BFS kann einen Graphen in der geringsten Anzahl von Iterationen durchlaufen.
- Die Architektur des BFS-Algorithmus ist einfach und robust.
- Das Ergebnis des BFS-Algorithmus weist im Vergleich zu anderen Algorithmen eine hohe Genauigkeit auf.
- BFS-Iterationen sind nahtlos und es besteht keine Möglichkeit, dass dieser Algorithmus in ein Endlosschleifenproblem gerät.
Wie funktioniert der BFS-Algorithmus?
Beim Durchlaufen von Graphen muss der Algorithmus jeden einzelnen nicht besuchten Knoten in einer baumartigen Struktur besuchen, prüfen und/oder aktualisieren. Diagrammdurchläufe werden nach der Reihenfolge kategorisiert, in der sie die Knoten im Diagramm besuchen.
Der BFS-Algorithmus startet die Operation vom ersten oder Startknoten in einem Diagramm und durchläuft diesen gründlich. Sobald der erste Knoten erfolgreich durchlaufen wurde, wird der nächste nicht durchlaufene Knoten im Diagramm besucht und markiert.
Daher kann man sagen, dass in der ersten Iteration alle Knoten, die an den aktuellen Knoten angrenzen, besucht und durchlaufen werden. Zur Implementierung des BFS-Algorithmus wird eine einfache Warteschlangenmethode verwendet, die aus folgenden Schritten besteht:
Schritt 1)
Jeder Scheitelpunkt oder Knoten im Diagramm ist bekannt. Sie können den Knoten beispielsweise als V markieren.
Schritt 2)
Falls auf den Knoten V nicht zugegriffen wird, wird der Knoten V in die BFS-Warteschlange eingefügt.
Schritt 3)
Starten Sie die BFS-Suche und markieren Sie nach deren Abschluss den Knoten V als besucht.
Schritt 4)
Die BFS-Warteschlange ist immer noch nicht leer. Entfernen Sie daher den Scheitelpunkt V des Diagramms aus der Warteschlange.
Schritt 5)
Ermitteln Sie alle verbleibenden Knoten im Graphen, die zum Knoten V benachbart sind.
Schritt 6)
Für jeden benachbarten Knoten, sagen wir V1, wird, falls dieser noch nicht besucht wurde, V1 der BFS-Warteschlange hinzugefügt.
Schritt 7)
BFS wird V1 besuchen, es als besucht markieren und aus der Warteschlange löschen.
Beispiel eines BFS-Algorithmus
Schritt 1)
Sie haben ein Diagramm mit sieben Zahlen im Bereich von 0 bis 6.
Schritt 2)
0 oder Null wurde als Wurzelknoten markiert.
Schritt 3)
0 wird besucht, markiert und in die Warteschlangendatenstruktur eingefügt.
Schritt 4)
Die verbleibenden 0-benachbarten und noch nicht besuchten Knoten werden besucht, markiert und in die Warteschlange eingefügt.
Schritt 5)
Durchlaufiterationen werden wiederholt, bis alle Knoten besucht sind.
Regeln des BFS-Algorithmus
Hier sind wichtige Regeln für die Verwendung des BFS-Algorithmus:
- Eine Warteschlange (FIFO – First in First Out) Datenstruktur wird von BFS verwendet.
- Man markiert einen beliebigen Knoten im Graphen als Wurzel und beginnt, die Daten von dort aus zu durchlaufen.
- BFS durchläuft alle Knoten im Graphen und speichert die gefundenen Knoten.ping sie als abgeschlossen.
- BFS besucht einen benachbarten, nicht besuchten Knoten, markiert ihn als erledigt und fügt ihn in eine Warteschlange ein.
- Falls kein benachbarter Knoten gefunden wird, wird der vorherige Knoten aus der Warteschlange entfernt.
- Der BFS-Algorithmus wird so lange wiederholt, bis alle Knoten im Graphen erfolgreich durchlaufen und als abgeschlossen markiert wurden.
- Beim Durchlaufen von Daten von einem Knoten werden durch BFS keine Schleifen verursacht.
Anwendungen des BFS-Algorithmus
Werfen wir einen Blick auf einige reale Anwendungen, bei denen die Implementierung eines BFS-Algorithmus äußerst effektiv sein kann.
- Ungewichtete Diagramme: Der BFS-Algorithmus kann auf einfache Weise den kürzesten Pfad und einen minimalen Spannbaum erstellen, um alle Knoten des Graphen in kürzester Zeit und mit hoher Genauigkeit zu besuchen.
- P2P-Netzwerke: Die Breitensuche (BFS) kann eingesetzt werden, um alle nächstgelegenen oder benachbarten Knoten in einem Peer-to-Peer-Netzwerk zu finden. Dadurch werden die benötigten Daten schneller gefunden.
- Webcrawler: Suchmaschinen oder Webcrawler können durch den Einsatz von BFS problemlos mehrere Indexebenen erstellen. Die BFS-Implementierung beginnt bei der Quelle, also der Webseite, und besucht dann alle Links von dieser Quelle.
- Navigationssysteme: BFS kann dabei helfen, alle benachbarten Standorte vom Haupt- oder Quellstandort aus zu finden.
- Netzwerkübertragung: Ein gesendetes Paket wird vom BFS-Algorithmus geleitet, um alle Knoten zu finden und zu erreichen, für die es die Adresse hat.
