Kas ir BFS?

Breadth-First Search (BFS) pamatā ir šķērsošanas mezgli, pievienojot katra mezgla kaimiņus šķērsošanas rindai, sākot no saknes mezgla. Grafika BFS ir līdzīga koka BFS, izņemot to, ka grafikos var būt cikli. Atšķirībā no dziļuma pirmās meklēšanas, visi blakus mezgli noteiktā dziļumā tiek izpētīti pirms pāriešanas uz nākamo līmeni.

BFS algoritms

Tālāk ir norādītas darbības, kas jāveic, lai izmantotu plašu meklēšanu, lai izpētītu diagrammu.

1. Ņemiet datus diagrammas blakus matricai vai blakus vietu sarakstam.
2. Izveidojiet rindu un piepildiet to ar vienumiem.
3. Aktivizējiet saknes mezglu (tas nozīmē, ka saknes mezgls tiek iegūts rindas sākumā).
4. Ievietojiet rindas galvgali (vai sākotnējo elementu) rindā, pēc tam ievietojiet rindā visus blakus esošos rindas mezglus no kreisās puses uz labo. Vienkārši noņemiet galviņu rindā un atsāciet darbību, ja mezglam tuvumā nav mezglu, kas būtu jāizpēta. (Piezīme. Ja parādās kaimiņš, kas ir iepriekš izmeklēts vai atrodas rindā, nelieciet to rindā; tā vietā izlaidiet to.)
5. Turpiniet šādā veidā, līdz rinda ir tukša.

BFS lietojumprogrammas

Algoritma elastības dēļ Breadth-First Search ir diezgan noderīga reālajā pasaulē. Šie ir daži no tiem:

1. Vienādranga tīklā tiek atklāti vienādranga mezgli. Lielākā daļa torrentu klientu, piemēram, BitTorrent, uTorrent un qBittorent, izmanto šo procesu, lai tīklā atrastu 'sēklas' un 'vienaudžus'.
2. Indekss ir izveidots, izmantojot diagrammu šķērsošanas paņēmienus tīmekļa pārmeklēšanā. Procedūra sākas ar avota lapu kā saknes mezglu un turpinās līdz visām sekundārajām lapām, kas ir saistītas ar avota lapu (un šis process turpinās). Tā kā rekursijas koka dziļums ir samazināts, meklēšanai platums vispirms ir raksturīga priekšrocība.
3. Izmantojot GPS navigācijas sistēmas, izmantojot GPS, veiciet plašu meklēšanu, lai atrastu tuvumā esošās vietas.
4. Atkritumu savākšanai tiek izmantota Čeinija tehnika, kas izmanto jēdzienu 'meklēšana pēc plašuma'.

BFS šķērsošanas piemērs

Lai sāktu, apskatīsim vienkāršu piemēru. Mēs sāksim ar 0 kā saknes mezglu un virzīsimies lejup pa grafiku.

1. darbība: Rinda (0)

Rinda

2. darbība: Rinda (0), rinda (1), rinda (3), rinda (4)

Rinda

3. darbība: Rinda (1), rinda (2)

Rinda

4. darbība: Rinda (3), rinda (5). Mēs rindai vairs nepievienosim, jo ​​0 jau ir izpētīts.

Rinda

5. darbība: Iekļauts rindā (4)

Rinda

6. darbība: Izlikt rindu (2)

Rinda

7. darbība: Iekļauts rindā (5)

Rinda

Rinda tagad ir tukša, tāpēc mēs apturēsim procesu.

Java programma Breadth-First Search

Ir vairākas pieejas, kā rīkoties ar kodu. Mēs galvenokārt apspriedīsim darbības, kas saistītas ar pirmās plašās meklēšanas ieviešanu Java. Grafiku glabāšanai var izmantot blakus esošo sarakstu vai blakus esošo matricu; jebkura metode ir pieņemama. Blakus saraksts tiks izmantots, lai attēlotu mūsu grafiku mūsu kodā. Ieviešot Java Breadth-First Search algoritmu, ir daudz vienkāršāk rīkoties ar blakus esošo sarakstu, jo mums ir jāpārvietojas cauri katram mezglam pievienoto mezglu sarakstam tikai tad, kad mezgls ir izņemts no rindas no sākuma (vai sākuma). rindā.

Grafiks, ko izmanto, lai demonstrētu kodu, būs identisks tam, kas tika izmantots iepriekšējā piemērā.

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