Kaj je BFS?

Iskanje najprej v širino (BFS) temelji na prečkanju vozlišč z dodajanjem sosedov vsakega vozlišča v čakalno vrsto prečkanja, začenši s korenskim vozliščem. BFS za graf je podoben tistemu za drevo, z izjemo, da imajo lahko grafi cikle. V nasprotju z iskanjem najprej v globino se vsa sosednja vozlišča na dani globini raziščejo, preden se nadaljuje na naslednjo raven.

Algoritem BFS

Sledijo koraki, vključeni v uporabo iskanja v širino za raziskovanje grafa:

1. Vzemite podatke za matriko sosednosti grafa ali seznam sosednosti.
2. Ustvarite čakalno vrsto in jo napolnite s predmeti.
3. Aktivirajte korensko vozlišče (kar pomeni, da dobite korensko vozlišče na začetku čakalne vrste).
4. Odstranite glavo čakalne vrste (ali začetni element), nato postavite v čakalno vrsto vsa bližnja vozlišča čakalne vrste od leve proti desni. Preprosto odstranite glavo iz vrste in nadaljujte z operacijo, če vozlišče nima bližnjih vozlišč, ki bi jih bilo treba raziskati. (Opomba: če se pojavi sosed, ki je bil že preiskan ali je v čakalni vrsti, ga ne postavite v čakalno vrsto; namesto tega ga preskočite.)
5. Nadaljujte na ta način, dokler ni čakalna vrsta prazna.

Aplikacije BFS

Zaradi prilagodljivosti algoritma je iskanje v širino precej uporabno v resničnem svetu. To je nekaj izmed njih:

1. V omrežju enakovrednih se odkrijejo enakovredna vozlišča. Večina torrent odjemalcev, kot so BitTorrent, uTorrent in qBittorent, uporablja ta postopek za iskanje 'semen' in 'vrstnikov' v omrežju.
2. Indeks je zgrajen s tehnikami prečkanja grafov pri spletnem pajkanju. Postopek se začne z izvorno stranjo kot korenskim vozliščem in nadaljuje pot do vseh sekundarnih strani, ki so povezane z izvorno stranjo (in ta postopek se nadaljuje). Zaradi zmanjšane globine rekurzijskega drevesa ima iskanje najprej v širino tukaj lastno prednost.
3. Uporaba navigacijskih sistemov GPS, ki uporabljajo GPS, opravi iskanje v širino, da poišče bližnja mesta.
4. Za zbiranje smeti se uporablja Cheneyjeva tehnika, ki uporablja koncept iskanja v širino.

Primer BFS Traversal

Za začetek si poglejmo preprost primer. Začeli bomo z 0 kot korenskim vozliščem in nadaljevali pot po grafu navzdol.

Korak 1: V čakalno vrsto (0)

Čakalna vrsta

2. korak: Iz vrste (0), iz vrste (1), iz vrste (3), iz vrste (4)

Čakalna vrsta

3. korak: Odstrani iz čakalne vrste (1), Izvrsti iz vrste (2)

Čakalna vrsta

4. korak: Odstrani iz vrste (3), Izvrsti iz vrste (5). 1 ne bomo znova dodali v čakalno vrsto, ker je 0 že raziskana.

Čakalna vrsta

5. korak: Odstranitev iz vrste (4)

Čakalna vrsta

6. korak: Odstranitev iz vrste (2)

Čakalna vrsta

7. korak: Odstranitev iz vrste (5)

Čakalna vrsta

Čakalna vrsta je zdaj prazna, zato bomo postopek ustavili.

Program Java za iskanje v širino

Obstaja več pristopov ravnanja s kodo. Večinoma bomo razpravljali o korakih, vključenih v implementacijo iskanja po širini v Javi. Za shranjevanje grafov je mogoče uporabiti seznam sosednosti ali matriko sosednosti; kateri koli način je sprejemljiv. Seznam sosednosti bo uporabljen za predstavitev našega grafa v naši kodi. Pri izvajanju algoritma iskanja najprej v širino v Javi je veliko lažje obravnavati seznam sosednosti, saj moramo potovati po seznamu vozlišč, ki so pritrjena na vsako vozlišče šele, ko je vozlišče izključeno iz čakalne vrste iz glave (ali začetka) čakalna vrsta.

Graf, uporabljen za predstavitev kode, bo enak tistemu, uporabljenemu v prejšnjem primeru.

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