BFS-Algorithmus (Breadth First Search) mit BEISPIEL

Inhaltsverzeichnis:

Anonim

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

Breadth-First-Search (BFS) ist ein Algorithmus, mit dem Daten grafisch dargestellt oder Bäume durchsucht oder Strukturen durchlaufen werden. Die vollständige Form von BFS ist die Breitensuche.

Der Algorithmus besucht und markiert effizient alle Schlüsselknoten in einem Diagramm in einer genauen Breite. Dieser Algorithmus wählt einen einzelnen Knoten (Anfangs- oder Quellpunkt) in einem Diagramm aus und besucht dann alle Knoten neben dem ausgewählten Knoten. Denken Sie daran, dass BFS nacheinander auf diese Knoten zugreift.

Sobald der Algorithmus den Startknoten besucht und markiert, bewegt er sich zu den nächsten nicht besuchten Knoten und analysiert diese. Nach dem Besuch werden alle Knoten markiert. Diese Iterationen werden fortgesetzt, bis alle Knoten des Diagramms erfolgreich besucht und markiert wurden.

In diesem Algorithmus-Tutorial lernen Sie:

  • Was ist der BFS-Algorithmus (Breadth-First Search)?
  • Was ist Graph Traversals?
  • Die Architektur des BFS-Algorithmus
  • Warum brauchen wir den BFS-Algorithmus?
  • Wie funktioniert der BFS-Algorithmus?
  • Beispiel BFS-Algorithmus
  • Regeln des BFS-Algorithmus
  • Anwendungen des BFS-Algorithmus

Was ist Graph Traversals?

Eine Diagrammdurchquerung ist eine häufig verwendete Methode zum Lokalisieren der Scheitelpunktposition im Diagramm. Es handelt sich um einen erweiterten Suchalgorithmus, mit dem der Graph schnell und präzise analysiert und die Reihenfolge der besuchten Scheitelpunkte markiert werden kann. Mit diesem Vorgang können Sie schnell jeden Knoten in einem Diagramm besuchen, ohne in einer Endlosschleife eingeschlossen zu sein.

Die Architektur des BFS-Algorithmus

  1. In den verschiedenen Datenebenen können Sie jeden Knoten als Start- oder Anfangsknoten markieren, um mit dem Durchlaufen zu beginnen. Das BFS besucht den Knoten und markiert ihn als besucht und stellt ihn in die Warteschlange.
  2. Jetzt besucht das BFS die nächsten und nicht besuchten Knoten und markiert sie. Diese Werte werden auch zur Warteschlange hinzugefügt. Die Warteschlange funktioniert nach dem FIFO-Modell.
  3. In ähnlicher Weise werden die verbleibenden nächsten und nicht besuchten Knoten im Diagramm markiert analysiert und der Warteschlange hinzugefügt. Diese Elemente werden als empfangen aus der Warteschlange gelöscht und als Ergebnis gedruckt.

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 Weg zum Durchlaufen dieser Knoten zu konstruieren.
  • BFS kann ein Diagramm 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 ein hohes Maß an 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, überprü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 sie gründlich. Sobald der ursprüngliche Knoten erfolgreich durchlaufen wurde, wird der nächste nicht durchquerte Scheitelpunkt im Diagramm besucht und markiert.

Daher können Sie sagen, dass alle Knoten neben dem aktuellen Scheitelpunkt in der ersten Iteration besucht und durchlaufen werden. Eine einfache Warteschlangenmethode wird verwendet, um die Funktionsweise eines BFS-Algorithmus zu implementieren. Sie besteht aus den folgenden Schritten:

Schritt 1)

Jeder Scheitelpunkt oder Knoten im Diagramm ist bekannt. Beispielsweise können Sie den Knoten als V markieren.

Schritt 2)

Wenn auf den Scheitelpunkt V nicht zugegriffen wird, fügen Sie den Scheitelpunkt V in die BFS-Warteschlange ein

Schritt 3)

Starten Sie die BFS-Suche und markieren Sie nach Abschluss Vertex 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 neben dem Scheitelpunkt V liegen

Schritt 6)

Nehmen wir für jeden benachbarten Scheitelpunkt V1 an, falls er noch nicht besucht wurde, und fügen Sie V1 zur BFS-Warteschlange hinzu

Schritt 7)

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

Beispiel BFS-Algorithmus

Schritt 1)

Sie haben eine Grafik mit sieben Zahlen zwischen 0 und 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)

Durchlaufende Iterationen werden wiederholt, bis alle Knoten besucht sind.

Regeln des BFS-Algorithmus

Hier sind wichtige Regeln für die Verwendung des BFS-Algorithmus:

  • Eine Warteschlangen-Datenstruktur (FIFO-First in First Out) wird von BFS verwendet.
  • Sie markieren einen beliebigen Knoten im Diagramm als root und beginnen, die Daten von ihm zu durchlaufen.
  • 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 Scheitelpunkte im Diagramm erfolgreich durchlaufen und als abgeschlossen markiert wurden.
  • Es gibt keine Schleifen, die durch BFS beim Durchlaufen von Daten von einem Knoten verursacht werden.

Anwendungen des BFS-Algorithmus

Werfen wir einen Blick auf einige reale Anwendungen, bei denen eine Implementierung eines BFS-Algorithmus sehr effektiv sein kann.

  • Ungewichtete Diagramme: Der BFS-Algorithmus kann auf einfache Weise den kürzesten Pfad und einen minimalen Spannbaum erstellen, um alle Scheitelpunkte des Diagramms in kürzester Zeit 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 mithilfe von BFS problemlos mehrere Indexebenen erstellen. Die BFS-Implementierung beginnt bei der Quelle, 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-Broadcasting: Ein gesendetes Paket wird vom BFS-Algorithmus geleitet, um alle Knoten zu finden und zu erreichen, für die es die Adresse hat.

Zusammenfassung

  • Ein Graph Traversal ist ein einzigartiger Prozess, bei dem der Algorithmus jeden einzelnen nicht besuchten Knoten in einer baumartigen Struktur besuchen, überprüfen und / oder aktualisieren muss. Der BFS-Algorithmus arbeitet nach einem ähnlichen Prinzip.
  • Der Algorithmus ist nützlich, um die Knoten in einem Diagramm zu analysieren und den kürzesten Weg zum Durchlaufen dieser Knoten zu konstruieren.
  • Der Algorithmus durchläuft den Graphen in der kleinsten 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 arbeitet nach dem Prinzip "First In First Out". 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 der robusten Implementierung wird BFS in mehreren realen Lösungen wie P2P-Netzwerken, Web Crawlern und Network Broadcasting verwendet.