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.
