Was ist BFS?
Die Breadth-First-Suche (BFS) basiert auf dem Durchlaufen von Knoten, indem die Nachbarn jedes Knotens ausgehend vom Wurzelknoten zur Durchquerungswarteschlange hinzugefügt werden. Der BFS für einen Graphen ähnelt dem eines Baumes, mit der Ausnahme, dass Graphen Zyklen haben können. Im Gegensatz zur Tiefensuche werden alle Nachbarknoten in einer bestimmten Tiefe untersucht, bevor zur nächsten Ebene übergegangen wird.
BFS-Algorithmus
Im Folgenden sind die Schritte aufgeführt, die bei der Verwendung der Breitensuche zur Untersuchung eines Diagramms erforderlich sind:
- Nehmen Sie die Daten für die Adjazenzmatrix oder Adjazenzliste des Diagramms.
- Erstellen Sie eine Warteschlange und füllen Sie sie mit Artikeln.
- Aktivieren Sie den Root-Knoten (was bedeutet, dass der Root-Knoten am Anfang der Warteschlange steht).
- Entfernen Sie den Kopf (oder das Anfangselement) der Warteschlange und stellen Sie dann alle nahegelegenen Knoten der Warteschlange von links nach rechts in die Warteschlange. Entfernen Sie einfach den Kopf aus der Warteschlange und setzen Sie den Vorgang fort, wenn ein Knoten keine Knoten in der Nähe hat, die untersucht werden müssen. (Hinweis: Wenn ein Nachbar auftaucht, der zuvor untersucht wurde oder sich in der Warteschlange befindet, stellen Sie ihn nicht in die Warteschlange, sondern überspringen Sie ihn.)
- Fahren Sie auf diese Weise fort, bis die Warteschlange leer ist.
BFS-Anwendungen
Aufgrund der Flexibilität des Algorithmus ist die Breitensuche in der realen Welt sehr nützlich. Dies sind einige davon:
wie man einen String in eine Ganzzahl umwandelt
- In einem Peer-to-Peer-Netzwerk werden Peer-Knoten erkannt. Die meisten Torrent-Clients wie BitTorrent, uTorrent und qBittorent verwenden diesen Prozess, um „Seeds“ und „Peers“ im Netzwerk zu finden.
- Der Index wird mithilfe von Graph-Traversal-Techniken beim Web-Crawling erstellt. Der Vorgang beginnt mit der Quellseite als Wurzelknoten und arbeitet sich nach unten zu allen sekundären Seiten vor, die mit der Quellseite verknüpft sind (und dieser Prozess wird fortgesetzt). Aufgrund der geringeren Tiefe des Rekursionsbaums hat die Breitensuche hier einen inhärenten Vorteil.
- Die Verwendung von GPS-Navigationssystemen führt mithilfe des GPS eine Breitensuche durch, um Standorte in der Nähe zu lokalisieren.
- Cheneys Technik, die das Konzept der Breitensuche verwendet, wird zum Sammeln von Müll verwendet.
Beispiel für eine BFS-Durchquerung
Schauen wir uns zunächst ein einfaches Beispiel an. Wir beginnen mit 0 als Wurzelknoten und arbeiten uns im Diagramm nach unten vor.
Schritt 1: In die Warteschlange stellen(0)
Warteschlange
| 0 |
Schritt 2: Dequeue(0), Enqueue(1), Enqueue(3), Enqueue(4)
Warteschlange
| 1 | 3 | 4 |
Schritt 3: Aus der Warteschlange entfernen(1), Einreihen(2)
Warteschlange
| 3 | 4 | 2 |
Schritt 4: Aus der Warteschlange entfernen(3), Einreihen(5). Wir werden 1 nicht erneut zur Warteschlange hinzufügen, da 0 bereits erkundet wurde.
Warteschlange
| 4 | 2 | 5 |
Schritt 5: Aus der Warteschlange(4)
Powershell-Kommentar mehrzeilig
Warteschlange
| 2 | 5 |
Schritt 6: Aus der Warteschlange(2)
Warteschlange
| 5 |
Schritt 7: Aus der Warteschlange(5)
Konvertieren einer Ganzzahl in eine Zeichenfolge
Warteschlange
Die Warteschlange ist jetzt leer, daher stoppen wir den Vorgang.
Java-Programm für die Breitensuche
Es gibt verschiedene Ansätze, mit dem Code umzugehen. Wir werden hauptsächlich die Schritte besprechen, die zur Implementierung einer Breitensuche in Java erforderlich sind. Zum Speichern von Diagrammen kann eine Adjazenzliste oder eine Adjazenzmatrix verwendet werden. Beide Methoden sind akzeptabel. Die Adjazenzliste wird verwendet, um unser Diagramm in unserem Code darzustellen. Bei der Implementierung des Breadth-First-Suchalgorithmus in Java ist es viel einfacher, mit der Adjazenzliste umzugehen, da wir nur die Liste der an jeden Knoten angehängten Knoten durchgehen müssen, sobald der Knoten vom Kopf (oder Anfang) des Knotens entfernt wird Warteschlange.
Das zur Veranschaulichung des Codes verwendete Diagramm ist mit dem im vorherigen Beispiel verwendeten Diagramm identisch.
BFSTraversal.java
import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>