Vad är BFS?

Breadth-First Search (BFS) baseras på att korsa noder genom att lägga till grannarna till varje nod till korsningskön med start från rotnoden. BFS för en graf liknar den för ett träd, med undantaget att grafer kan ha cykler. I motsats till djup-först-sökning, undersöks alla grannnoder på ett givet djup innan man fortsätter till nästa nivå.

BFS-algoritm

Följande är stegen som är involverade i att använda bredd-först-sökning för att utforska en graf:

1. Ta data för grafens angränsande matris eller angränsande lista.
2. Skapa en kö och fyll den med föremål.
3. Aktivera rotnoden (vilket betyder att få rotnoden i början av kön).
4. Ta bort köns huvud (eller initialelement), ställ sedan alla köns närliggande noder i kö från vänster till höger. Ställ helt enkelt ut huvudet och återuppta operationen om en nod inte har några närliggande noder som behöver undersökas. (Obs: Om en granne dyker upp som tidigare har undersökts eller står i kön, ställ inte den i kö, utan hoppa över den.)
5. Fortsätt på detta sätt tills kön är tom.

BFS-applikationer

På grund av algoritmens flexibilitet är Breadth-First Search ganska användbart i den verkliga världen. Det här är några av dem:

1. I ett peer-to-peer-nätverk upptäcks peer-noder. De flesta torrentklienter, som BitTorrent, uTorrent och qBittorent, använder denna process för att hitta 'frön' och 'kamrater' i nätverket.
2. Indexet är byggt med hjälp av graftraversaltekniker vid webbcrawlning. Proceduren börjar med källsidan som rotnod och arbetar sig ner till alla sekundära sidor som är länkade till källsidan (och denna process fortsätter). På grund av det minskade djupet på rekursionsträdet har Breadth-First Search en inneboende fördel här.
3. Användningen av GPS-navigeringssystem som använder GPS, gör en sökning först för att hitta närliggande platser.
4. Cheneys teknik, som använder konceptet bredd-först-sökning, används för att samla in sopor.

Exempel BFS Traversal

För att komma igång, låt oss titta på ett enkelt exempel. Vi börjar med 0 som rotnod och arbetar oss ner i grafen.

påskägg i Android

Steg 1: Kö(0)

Kö

Steg 2: Dequeue(0), Enqueue(1), Enqueue(3), Enqueue(4)

Kö

Steg 3: Dequeue(1), Enqueue(2)

hur man kör ett skript

Kö

Steg 4: Dequeue(3), Enqueue(5). Vi kommer inte att lägga till 1 i kön igen eftersom 0 redan har utforskats.

Kö

Steg 5: Avkö(4)

Kö

hur stor är min datorskärm

Steg 6: Avkö(2)

Kö

min live cricket

Steg 7: Avkö(5)

Kö

Kön är tom nu så vi stoppar processen.

Breadth-First Search Java-program

Det finns flera sätt att hantera koden. Vi kommer mestadels att diskutera stegen som är involverade i implementeringen av en bred första sökning i Java. En närliggande lista eller en närliggande matris kan användas för att lagra grafer; båda metoderna är acceptabla. Närliggande lista kommer att användas för att representera vår graf i vår kod. När du implementerar Breadth-First Search-algoritmen i Java är det mycket lättare att hantera närliggande lista eftersom vi bara behöver gå igenom listan med noder som är kopplade till varje nod när noden har tagits ur kö från huvudet (eller början) av kö.

Grafen som används för att demonstrera koden kommer att vara identisk med den som användes i föregående exempel.

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;>