Breiten-Suchalgorithmus: Übersicht, Bedeutung & Anwendungen

Grafiken sind überall um uns herum. Ein Graph kann als ein miteinander verbundenes Netzwerk von Knoten und Kanten betrachtet werden. Ihre Freunde auf Facebook, Ihre Verbindungen auf LinkedIn oder Ihre Twitter/Instagram-Follower bilden Ihr Social Graph. Wenn Sie von Punkt A nach Punkt B gelangen möchten, können Sie dies auf ähnliche Weise über mehrere Routen tun, die auf Google Maps visualisiert werden können.

Alle diese mehrfachen Routenoptionen von Punkt A nach Punkt B bilden ebenfalls einen Graphen. Graphen gehören zu den häufigsten Datenstrukturen, denen wir in der Wissenschaft und in der realen Welt gleichermaßen begegnen, weil sie so allgegenwärtig sind. Und eine der häufigsten Operationen, die an einem Graphen durchgeführt werden können, ist das Traversieren des Graphen.

Was ist Graphtraversal?

Graph Traversal ist eine Methode, um jeden Knoten in einem Graphen genau einmal schnell und präzise zu besuchen. Es ist ein fortschrittlicher Graph-Suchalgorithmus, der es Ihnen ermöglicht, die Sequenz der besuchten Knoten zu drucken, ohne in einer Endlosschleife gefangen zu sein. Es gibt viele Graph-Traversal-Algorithmen wie Tiefensuche , Breitensuche , Djikstra - Algorithmus , A -Star-Algorithmus und mehr.

Dieser Artikel wird einen tiefen Einblick in den Breadth First Search Algorithm oder BFS geben.

Diagrammstruktur

Bevor wir einen detaillierten Blick unter die BFS-Haube werfen, machen wir uns mit Hilfe der obigen Grafik mit einigen Graph-Terminologien vertraut:

Stammknoten – Der Knoten, an dem Sie den Traversierungsprozess starten. Der Einfachheit halber können wir A als Wurzelknoten betrachten.

Ebenen – Eine Ebene ist eine Sammlung aller Knoten, die gleich weit vom Wurzelknoten entfernt sind. Wenn wir also Knoten A auf Ebene 0 betrachten, befinden sich Knoten B und C auf Ebene 1, während Knoten D, E und F auf Ebene 2 liegen. Eine einfache Heuristik zur Bestimmung der Ebenennummer eines Knotens besteht darin, die Nummer zu zählen von Kanten zwischen dem Knoten und dem Wurzelknoten. Beachten Sie, dass dies nur funktioniert, wenn Sie den Wurzelknoten auf Ebene 0 definieren.

Übergeordneter Knoten – Der übergeordnete Knoten eines Knotens ist derjenige, der sich eine Ebene darüber und neben ihm befindet. Er kann als der Knoten betrachtet werden, von dem der Knoten stammt. A ist der übergeordnete Knoten von B und C.

Untergeordnete / Untergeordnete Knoten – Knoten, die abzweigen und an einen übergeordneten Knoten angrenzen. B und C sind untergeordnete Knoten von A

Lesen Sie: Top 10 Datenvisualisierungstechniken

BFS ist ein Graph-Traversal-Algorithmus, um einen Baum oder einen Graphen effizient zu erkunden. Der Algorithmus beginnt mit einem Anfangsknoten (Root-Knoten) und fährt dann damit fort, alle angrenzenden Knoten in der Breite zuerst zu untersuchen, im Gegensatz zur Tiefe zuerst, die einen bestimmten Zweig bis zu allen Knoten in diesem Zweig hinuntergeht werden besucht. Einfach ausgedrückt, es durchquert den Graphen ebenenweise und bewegt sich nicht eine Ebene nach unten, bis alle Knoten in dieser Ebene besucht und markiert sind.

Es arbeitet nach dem First-In-First-Out-Prinzip (FIFO) und wird unter Verwendung einer Warteschlangen-Datenstruktur implementiert. Sobald ein Knoten besucht wird, wird er in eine Warteschlange eingefügt. Dann wird er aufgezeichnet und alle seine untergeordneten Knoten werden in die Warteschlange eingefügt. Dieser Prozess wird fortgesetzt, bis alle Knoten im Diagramm besucht und aufgezeichnet sind.

Schauen wir uns die detaillierten Warteschlangenoperationen für den BFS-Algorithmus für den oben angegebenen Graphen an:

() – bezeichnet die Warteschlange

[] – bezeichnet die gedruckte Ausgabe

1. A in die Warteschlange einfügen (a)
2. Drucke A, füge B und C in die Warteschlange ein (cb)[a]
3. Drucke B, füge seine untergeordneten Knoten D und E in die Warteschlange ein (edc)[ba]
4. Gib C aus, füge seinen Kindknoten F in die Warteschlange ein (fed)[cba]
5. Drucken Sie D, fügen Sie seinen untergeordneten Knoten in die Warteschlange ein. Da sind keine. (fe)[dcba]
6. Gib E aus, dessen Kindknoten F bereits in die Warteschlange eingefügt wurde. (f)[edcba]
7. Drucken F. [fedcba]

Was den BFS-Algorithmus wichtig macht

Es gibt unzählige Gründe, BFS als Methode zum schnellen Durchsuchen großer Datensätze einzusetzen. Einige der herausragenden Merkmale, die es zur bevorzugten Wahl für Entwickler und Dateningenieure machen, sind:

• BFS kann effektiv alle Knoten im Diagramm erkunden und den kürzestmöglichen Weg finden, um sie alle zu erkunden.
• Die Anzahl der Iterationen, die erforderlich ist, um den gesamten Graphen zu durchlaufen, ist geringer als bei anderen Suchalgorithmen.
• Da es unter Verwendung einer Warteschlange implementiert wird, ist seine Architektur robust, zuverlässig und elegant.
• Im Vergleich zu anderen Algorithmen ist die Ausgabe von BFS exakt und fehlerfrei.
• BFS-Iterationen laufen reibungslos, ohne Gefahr zu laufen, in einer Endlosschleife gefangen zu werden.

Checkout: Datenvisualisierungsprojekte, die Sie replizieren können

Anwendungen des BFS-Algorithmus

Aufgrund seiner Einfachheit und einfachen Einrichtung hat der BFS-Algorithmus eine weit verbreitete Verwendung in verschiedenen Schlüsselsituationen der realen Welt gefunden. Sehen wir uns einige prominente Anwendungen an:

Suchmaschinen-Crawler – Stellen Sie sich eine Welt ohne Google oder Bing vor. Du kannst nicht. Suchmaschinen sind das Rückgrat des Internets. Und der BFS-Algorithmus ist das Rückgrat von Suchmaschinen. Es ist der primäre Algorithmus, der zum Indexieren von Webseiten verwendet wird. Der Algorithmus beginnt seine Reise von der Quellseite (Stammknoten) und folgt dann allen Links auf dieser Quellseite der Breite nach. Jede Webseite kann als unabhängiger Knoten im Diagramm betrachtet werden.

Ungewichtete Graphdurchläufe – BFS kann den kürzesten Pfad und den minimalen Spannbaum in einem ungewichteten Graphen identifizieren. Beim Finden der kürzesten Route geht es lediglich darum, einen Weg mit der geringsten Anzahl von Kanten zu finden, wofür BFS ideal geeignet ist. Es kann Arbeit erledigen, indem es die geringste Anzahl von Knoten besucht.

GPS-Navigation – BFS nutzt die GPS-Systeme, um alle möglichen Nachbarorte von Ihrem Startpunkt aus aufzudecken und Ihnen dabei zu helfen, nahtlos von Punkt A nach B zu navigieren.

Broadcasting – Broadcast-Netzwerke verwenden Pakete als Einheiten, um Signale und Daten zu übertragen. Der BFS-Algorithmus lenkt diese Pakete so, dass sie zu allen Knoten im Netzwerk gelangen, die sie erreichen sollen.

P2P-Netzwerke – Torrents oder andere Filesharing-Netzwerke verlassen sich auf die P2P-Kommunikation. BFS funktioniert hervorragend, um die nächstgelegenen Knoten zu finden, damit die Datenübertragung schneller erfolgen kann.

Lesen Sie auch: Vorteile der Datenvisualisierung

Fazit

Ergo ist der Breadth First Search Algorithmus einer der wichtigsten Algorithmen des modernen Internets. Hoffentlich dient dieser Blog als praktischer Ausgangspunkt für Ihre Erkundungen von Suchalgorithmen.

Wir empfehlen Ihnen, das von IIIT Bangalore angebotene PG-Diplom in Data Science zu wählen, das auf upGrad gehostet wird, da Sie hier Ihre Fragen 1-1 mit den Kursleitern stellen können. Es konzentriert sich nicht nur auf theoretisches Lernen, sondern legt Wert auf praktisches Wissen, das unerlässlich ist, um die Lernenden auf reale Projekte vorzubereiten und Ihnen das erste NASSCOM-Zertifikat Indiens zu verleihen, das Ihnen hilft, hochbezahlte Jobs in Data Science zu bekommen.