Wat is BFS?
Breadth-First Search (BFS) is gebaseerd op het doorlopen van knooppunten door de buren van elk knooppunt toe te voegen aan de traversale wachtrij, beginnend bij het hoofdknooppunt. De BFS voor een grafiek is vergelijkbaar met die van een boom, met de uitzondering dat grafieken cycli kunnen hebben. In tegenstelling tot diepte-eerst zoeken worden alle aangrenzende knooppunten op een bepaalde diepte onderzocht voordat naar het volgende niveau wordt gegaan.
BFS-algoritme
Hieronder volgen de stappen die betrokken zijn bij het gebruik van breedte-eerst zoeken om een grafiek te verkennen:
- Neem de gegevens voor de aangrenzende matrix of aangrenzende lijst van de grafiek.
- Creëer een wachtrij en vul deze met items.
- Activeer het hoofdknooppunt (wat betekent dat u het hoofdknooppunt aan het begin van de wachtrij krijgt).
- Haal de kop van de wachtrij (of het initiële element) uit de wachtrij en zet vervolgens alle nabijgelegen knooppunten van de wachtrij van links naar rechts in de wachtrij. Haal eenvoudigweg de kop uit de wachtrij en hervat de bewerking als een knooppunt geen knooppunten in de buurt heeft die moeten worden onderzocht. (Opmerking: als er een buurman opduikt die eerder is onderzocht of die in de wachtrij staat, zet hem dan niet in de wachtrij; sla hem in plaats daarvan over.)
- Ga op deze manier door totdat de wachtrij leeg is.
BFS-toepassingen
Vanwege de flexibiliteit van het algoritme is Breadth-First Search behoorlijk nuttig in de echte wereld. Dit zijn er enkele:
- In een peer-to-peer-netwerk worden peer-nodes ontdekt. De meeste torrent-clients, zoals BitTorrent, uTorrent en qBittorent, gebruiken dit proces om 'seeds' en 'peers' in het netwerk te vinden.
- De index is opgebouwd met behulp van grafiekdoorlooptechnieken bij het webcrawlen. De procedure begint met de bronpagina als hoofdknooppunt en werkt door naar alle secundaire pagina's die aan de bronpagina zijn gekoppeld (en dit proces gaat door). Vanwege de verminderde diepte van de recursieboom heeft Breadth-First Search hier een inherent voordeel.
- Het gebruik van GPS-navigatiesystemen die gebruik maken van GPS, voert een breedte-eerste zoekopdracht uit om nabijgelegen locaties te lokaliseren.
- Cheney's techniek, die gebruik maakt van het concept van 'breedte-eerst zoeken', wordt gebruikt om afval te verzamelen.
Voorbeeld BFS-traversal
Laten we om te beginnen eens kijken naar een eenvoudig voorbeeld. We beginnen met 0 als het hoofdknooppunt en werken naar beneden in de grafiek.
roep een js-functie aan vanuit html
Stap 1: In wachtrij(0)
Wachtrij
| 0 |
Stap 2: In wachtrij plaatsen(0), In wachtrij plaatsen(1), In wachtrij plaatsen(3), In wachtrij plaatsen(4)
Wachtrij
| 1 | 3 | 4 |
Stap 3: In wachtrij plaatsen(1), In wachtrij plaatsen(2)
object naar string converteren
Wachtrij
| 3 | 4 | 2 |
Stap 4: In wachtrij plaatsen(3), In wachtrij plaatsen(5). We zullen niet opnieuw 1 aan de wachtrij toevoegen omdat 0 al is verkend.
Wachtrij
| 4 | 2 | 5 |
Stap 5: Uit de wachtrij halen(4)
Wachtrij
zweven in css
| 2 | 5 |
Stap 6: Uit wachtrij(2)
Wachtrij
java boolean naar string
| 5 |
Stap 7: Uit de wachtrij halen(5)
Wachtrij
De wachtrij is nu leeg, dus we stoppen het proces.
Broadth-First Search Java-programma
Er zijn verschillende benaderingen om met de code om te gaan. We bespreken vooral de stappen die betrokken zijn bij het implementeren van een breedte-eerste zoekopdracht in Java. Een aangrenzende lijst of een aangrenzende matrix kan worden gebruikt om grafieken op te slaan; beide methoden zijn acceptabel. De aangrenzende lijst zal worden gebruikt om onze grafiek in onze code weer te geven. Bij het implementeren van het Breadth-First Search-algoritme in Java is het veel eenvoudiger om met de aangrenzende lijst om te gaan, omdat we alleen door de lijst met knooppunten hoeven te reizen die aan elk knooppunt zijn gekoppeld zodra het knooppunt uit de wachtrij is gehaald vanaf het hoofd (of begin) van het knooppunt. wachtrij.
De grafiek die wordt gebruikt om de code te demonstreren zal identiek zijn aan die in het vorige voorbeeld.
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;>