Algorithmus der Breitensuche (BFS) mit BEISPIEL

Was ist der BFS-Algorithmus (Breadth-First Search)?

Die Breitensuche (BFS) ist ein Algorithmus, der zum Zeichnen von Daten oder zum Durchsuchen von Bäumen oder Durchlaufen von Strukturen verwendet wird. Die Langform von BFS lautet 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

1. In den verschiedenen Datenebenen können Sie jeden Knoten als Start- oder Anfangsknoten markieren, mit dem die Durchquerung beginnen soll. Das BFS besucht den Knoten, markiert ihn als besucht und stellt ihn in die Warteschlange.
2. Nun besucht das BFS die nächsten und noch nicht besuchten Knoten und markiert sie. Diese Werte werden ebenfalls zur Warteschlange hinzugefügt. Die Warteschlange arbeitet auf der FIFO-Modell.
3. Auf ähnliche Weise werden die verbleibenden nächsten und nicht besuchten Knoten im Diagramm analysiert, markiert und der Warteschlange hinzugefügt. Diese Elemente werden beim Empfang aus der Warteschlange gelöscht und als Ergebnis ausgedruckt.

Warum brauchen wir den BFS-Algorithmus?

Es gibt zahlreiche Gründe, den BFS-Algorithmus für die Suche nach Ihrem Datensatz zu verwenden. Einige der wichtigsten Aspekte, die diesen Algorithmus zu Ihrer 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.

Man kann also sagen, dass alle Knoten, die an den aktuellen Scheitelpunkt angrenzen, in der ersten Iteration besucht und durchlaufen werden. Zur Implementierung der Funktionsweise eines BFS-Algorithmus wird eine einfache Warteschlangenmethode verwendet, die aus den 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 Scheitelpunkt V nicht zugegriffen wird, fügen Sie den Scheitelpunkt V zur BFS-Warteschlange hinzu

Schritt 3)

Starten Sie die BFS-Suche und markieren Sie nach Abschluss den Scheitelpunkt 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)

Rufen Sie alle verbleibenden Scheitelpunkte im Diagramm ab, die an den Scheitelpunkt V angrenzen

Schritt 6)

Für jeden benachbarten Scheitelpunkt sagen wir V1. Falls er noch nicht besucht wurde, fügen Sie V1 zur BFS-Warteschlange hinzu

Schritt 7)

BFS besucht V1, markiert es als besucht und löscht es aus der Warteschlange.

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 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.
• Sie markieren einen beliebigen Knoten im Diagramm als Stammknoten und beginnen von dort aus mit dem Durchlaufen der Daten.
• BFS durchläuft alle Knoten im Diagramm und löscht sie weiterhin als abgeschlossen.
• BFS besucht einen benachbarten, nicht besuchten Knoten, markiert ihn als erledigt und fügt ihn in eine Warteschlange ein.
• Entfernt den vorherigen Scheitelpunkt aus der Warteschlange, falls kein benachbarter Scheitelpunkt gefunden wird.
• Der BFS-Algorithmus iteriert, bis alle Eckpunkte im Diagramm 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 problemlos den kürzesten Pfad und einen minimalen Spannbaum erstellen, um alle Eckpunkte des Diagramms in kürzester Zeit und mit hoher Genauigkeit zu besuchen.
• P2P-Netzwerke: BFS kann implementiert werden, um alle nächsten oder benachbarten Knoten in einem Peer-to-Peer-Netzwerk zu lokalisieren. Dadurch werden die erforderlichen 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.

Zusammenfassung

• Eine Graphendurchquerung ist ein einzigartiger Prozess, bei dem der Algorithmus jeden einzelnen nicht besuchten Knoten in einer baumartigen Struktur besuchen, prüfen und/oder aktualisieren muss. Der BFS-Algorithmus funktioniert nach einem ähnlichen Prinzip.
• Der Algorithmus ist nützlich, um die Knoten in einem Diagramm zu analysieren und den kürzesten Weg durch diese zu konstruieren.
• Der Algorithmus durchläuft den Graphen in der geringsten Anzahl von Iterationen und in der kürzestmöglichen Zeit.
• BFS wählt einen einzelnen Knoten (Anfangs- oder Quellpunkt) in einem Diagramm aus und besucht dann alle Knoten neben dem ausgewählten Knoten. BFS greift nacheinander auf diese Knoten zu.
• Die besuchten und markierten Daten werden von BFS in eine Warteschlange gestellt. Eine Warteschlange funktioniert nach dem First-In-First-Out-Prinzip. Daher wird das zuerst im Diagramm platzierte Element zuerst gelöscht und als Ergebnis gedruckt.
• Der BFS-Algorithmus kann niemals in eine Endlosschleife geraten.
• Aufgrund der hohen Präzision und robusten Implementierung wird BFS in mehreren realen Lösungen wie P2P-Netzwerken, Web Crawlern und Network Broadcasting verwendet.