Mikä on BFS?

Breadth-First Search (BFS) perustuu solmujen läpikulkuun lisäämällä kunkin solmun naapurit läpikulkujonoon juurisolmusta alkaen. Kuvaajan BFS on samanlainen kuin puun, paitsi että kaavioissa voi olla jaksoja. Toisin kuin syvyyshaku, kaikki tietyllä syvyydellä olevat naapurisolmut tutkitaan ennen seuraavalle tasolle siirtymistä.

BFS-algoritmi

Seuraavat ovat vaiheet, jotka liittyvät leveyshaun käyttämiseen kaavion tutkimiseen:

1. Ota graafin viereisyysmatriisin tai viereisyysluettelon tiedot.
2. Luo jono ja täytä se kohteilla.
3. Aktivoi juurisolmu (eli saa juurisolmun jonon alussa).
4. Aseta jonon pää (tai alkuelementti) jonoon ja aseta sitten kaikki jonon lähellä olevat solmut jonoon vasemmalta oikealle. Poista pää jonosta ja jatka toimintoa, jos solmulla ei ole lähellä olevia solmuja, jotka olisi tutkittava. (Huomaa: Jos esiin tulee naapuri, joka on aiemmin tutkittu tai joka on jonossa, älä laita sitä jonoon, vaan ohita se.)
5. Jatka tällä tavalla, kunnes jono on tyhjä.

BFS-sovellukset

Algoritmin joustavuuden vuoksi Breadth-First Search on varsin hyödyllinen todellisessa maailmassa. Tässä muutamia niistä:

1. Vertaisverkossa vertaissolmut löydetään. Useimmat torrent-asiakkaat, kuten BitTorrent, uTorrent ja qBittorent, käyttävät tätä prosessia löytääkseen 'siemeniä' ja 'peersiä' verkosta.
2. Hakemisto on rakennettu käyttämällä verkkoindeksoinnin kaavion läpikulkutekniikoita. Toimenpide alkaa lähdesivusta juurisolmuna ja jatkuu kaikille toissijaisille sivuille, jotka on linkitetty lähdesivulle (ja tämä prosessi jatkuu). Rekursiopuun pienentyneen syvyyden vuoksi Breadth-First -haulla on tässä luontainen etu.
3. GPS-navigointijärjestelmien käyttö GPS:n avulla, suorita leveyshaku lähellä olevien paikkojen löytämiseksi.
4. Roskien keräämiseen käytetään Cheneyn tekniikkaa, joka käyttää leveyshakua.

Esimerkki BFS:n läpikäymisestä

Aloita katsomalla yksinkertaista esimerkkiä. Aloitamme 0:sta juurisolmuna ja jatkamme kaaviota alaspäin.

Vaihe 1: Jono (0)

Jonottaa

Vaihe 2: Jono(0), Jono(1), Jono(3), Jono(4)

Jonottaa

Vaihe 3: Jono(1), Jono(2)

Jonottaa

Vaihe 4: Jono(3), Jono(5). Emme lisää 1:tä jonoon uudelleen, koska 0 on jo tutkittu.

Jonottaa

Vaihe 5: Jonosta (4)

Jonottaa

Vaihe 6: Laita jonoon (2)

Jonottaa

Vaihe 7: Jonosta (5)

Jonottaa

Jono on nyt tyhjä, joten lopetamme prosessin.

Breadth-First Search Java-ohjelma

Koodin käsittelyyn on useita tapoja. Keskustelemme enimmäkseen vaiheista, jotka liittyvät laajan ensimmäisen haun toteuttamiseen Javassa. Graafeiden tallentamiseen voidaan käyttää viereisyysluetteloa tai viereisyysmatriisia; kumpi tahansa menetelmä on hyväksyttävä. Viereisyysluetteloa käytetään kuvaamaan kaavioamme koodissamme. Toteutettaessa Breadth-First Search -algoritmia Javassa on paljon helpompaa käsitellä vierekkäisyyttä, koska meidän tarvitsee vain kulkea jokaiseen solmuun liitettyjen solmujen luettelon läpi, kun solmu on purettu jonosta jonottaa.

Koodia kuvaava kaavio on identtinen edellisessä esimerkissä käytetyn kanssa.

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