Što je BFS?
Pretraživanje prvo u širinu (BFS) temelji se na prelaženju čvorova dodavanjem susjeda svakog čvora u red čekanja prelaženja počevši od korijenskog čvora. BFS za graf sličan je onom za stablo, s tim da grafovi mogu imati cikluse. Za razliku od pretraživanja u dubinu, svi susjedni čvorovi na danoj dubini se istražuju prije prelaska na sljedeću razinu.
BFS algoritam
Sljedeći su koraci uključeni u korištenje pretraživanja u širinu za istraživanje grafikona:
- Uzmite podatke za matricu susjedstva ili popis susjednosti grafa.
- Napravite red čekanja i popunite ga stavkama.
- Aktivirajte korijenski čvor (što znači da dobijete korijenski čvor na početku reda čekanja).
- Uklonite glavu reda (ili početni element) iz reda čekanja, zatim stavite u red čekanja sve obližnje čvorove reda slijeva na desno. Jednostavno uklonite glavu iz reda čekanja i nastavite s operacijom ako čvor nema čvorove u blizini koje je potrebno istražiti. (Napomena: Ako se pojavi susjed koji je prethodno istražen ili je u redu čekanja, nemojte ga stavljati u red; umjesto toga ga preskočite.)
- Nastavite na ovaj način dok se red ne isprazni.
BFS aplikacije
Zbog fleksibilnosti algoritma, Breadth-First Search vrlo je korisna u stvarnom svijetu. Ovo su neki od njih:
- U peer-to-peer mreži, peer čvorovi se otkrivaju. Većina torrent klijenata, kao što su BitTorrent, uTorrent i qBittorent, koriste ovaj proces za pronalaženje 'seedova' i 'peera' u mreži.
- Indeks je izgrađen pomoću tehnika obilaženja grafa u indeksiranju weba. Postupak počinje s izvornom stranicom kao korijenskim čvorom i ide prema dolje do svih sekundarnih stranica koje su povezane s izvornom stranicom (i taj se proces nastavlja). Zbog smanjene dubine rekurzivnog stabla, pretraživanje prvo u širinu ovdje ima inherentnu prednost.
- Korištenje GPS navigacijskih sustava koji koriste GPS, provedite pretraživanje u širinu kako biste locirali obližnja mjesta.
- Za skupljanje smeća koristi se Cheneyjeva tehnika, koja koristi koncept pretraživanja u širinu.
Primjer BFS Traversal
Za početak, pogledajmo jednostavan primjer. Počet ćemo s 0 kao korijenskim čvorom i krenuti niz graf.
Korak 1: Stavi u red (0)
Red
| 0 |
Korak 2: Dequeue(0), Enqueue(1), Enqueue(3), Enqueue(4)
Red
| 1 | 3 | 4 |
Korak 3: Dequeue(1), Enqueue(2)
Red
| 3 | 4 | 2 |
Korak 4: Dequeue(3), Enqueue(5). Nećemo ponovno dodati 1 u red jer je 0 već istražen.
Red
| 4 | 2 | 5 |
Korak 5: Izbaci iz reda (4)
Red
| 2 | 5 |
Korak 6: Izbaci iz reda (2)
Red
| 5 |
Korak 7: Izbaci iz reda (5)
Red
Red čekanja je sada prazan pa ćemo zaustaviti proces.
Java program pretraživanja u širinu
Postoji nekoliko pristupa postupanju s kodom. Uglavnom ćemo raspravljati o koracima uključenim u implementaciju pretraživanja najprije u širinu u Javi. Popis susjedstva ili matrica susjedstva mogu se koristiti za pohranjivanje grafova; obje metode su prihvatljive. Popis susjedstva će se koristiti za predstavljanje našeg grafa u našem kodu. Kada implementiramo algoritam pretraživanja prvo u širinu u Javi, mnogo je lakše nositi se s popisom susjedstva budući da moramo putovati kroz popis čvorova koji su pripojeni svakom čvoru nakon što je čvor uklonjen iz reda čekanja s glave (ili početka) red.
Graf korišten za demonstraciju koda bit će identičan onom korištenom u prethodnom primjeru.
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;>