čo je BFS?

Breadth-First Search (BFS) je založené na prechádzaní uzlov pridaním susedov každého uzla do frontu prechodu, ktorý začína od koreňového uzla. BFS pre graf je podobný ako pre strom, s výnimkou toho, že grafy môžu mať cykly. Na rozdiel od hĺbkového vyhľadávania sú všetky susedné uzly v danej hĺbke vyšetrené pred pokračovaním na ďalšiu úroveň.

Algoritmus BFS

Nasledovné sú kroky, ktoré sa týkajú použitia šírkového vyhľadávania na preskúmanie grafu:

1. Vezmite údaje pre maticu susednosti grafu alebo zoznam priľahlosti.
2. Vytvorte rad a naplňte ho položkami.
3. Aktivujte koreňový uzol (to znamená, že dostanete koreňový uzol na začiatok frontu).
4. Zaraďte do frontu hlavu (alebo počiatočný prvok) a potom zaraďte všetky blízke uzly frontu zľava doprava. Jednoducho vyraďte hlavu a pokračujte v operácii, ak uzol nemá žiadne blízke uzly, ktoré je potrebné preskúmať. (Poznámka: Ak sa objaví sused, ktorý už bol vyšetrovaný alebo je vo fronte, nezaraďujte ho do poradia, ale preskočte ho.)
5. Pokračujte týmto spôsobom, kým nebude front prázdny.

Aplikácie BFS

Vďaka flexibilite algoritmu je vyhľadávanie na prvom mieste v reálnom svete veľmi užitočné. Toto sú niektoré z nich:

1. V sieti typu peer-to-peer sa zisťujú uzly typu peer. Väčšina torrent klientov, ako sú BitTorrent, uTorrent a qBittorent, využíva tento proces na nájdenie „semien“ a „rovesníkov“ v sieti.
2. Index je vytvorený pomocou techník prechádzania grafov pri prehľadávaní webu. Procedúra začína zdrojovou stránkou ako koreňovým uzlom a postupuje smerom nadol na všetky sekundárne stránky, ktoré sú prepojené so zdrojovou stránkou (a tento proces pokračuje). Vzhľadom na zníženú hĺbku stromu rekurzie má v tomto prípade vyhľadávanie na prvom mieste podstatnú výhodu.
3. Pomocou navigačných systémov GPS, ktoré využívajú GPS, vykonajte najskôr vyhľadávanie na šírku, aby ste našli miesta v okolí.
4. Na zber odpadu sa používa Cheneyho technika, ktorá využíva koncept vyhľadávania do šírky.

Príklad BFS Traversal

Na začiatok sa pozrime na jednoduchý príklad. Začneme s 0 ako koreňovým uzlom a postupujeme smerom nadol v grafe.

Krok 1: Zaradiť (0)

Fronta

Krok 2: Zaradiť (0), Zaradiť (1), Zaradiť (3), Zaradiť (4)

Fronta

Krok 3: Zoradiť (1), Zoradiť (2)

Fronta

faktoriál v c

Krok 4: Dequeue (3), Enqueue (5). 1 do poradia znova nepridáme, pretože 0 už bola preskúmaná.

Fronta

Krok 5: Dequeue (4)

Fronta

Krok 6: Dequeue (2)

Fronta

Krok 7: Dequeue (5)

Fronta

Front je teraz prázdny, takže proces zastavíme.

Program Java na vyhľadávanie na prvom mieste

Existuje niekoľko prístupov, ako sa vysporiadať s kódom. Väčšinou budeme diskutovať o krokoch, ktoré sú súčasťou implementácie šírkového vyhľadávania v jazyku Java. Na uloženie grafov možno použiť zoznam susedstva alebo maticu susedstva; ktorýkoľvek spôsob je prijateľný. Zoznam susedstva sa použije na znázornenie nášho grafu v našom kóde. Pri implementácii algoritmu Breadth-First Search v jazyku Java je oveľa jednoduchšie zaobchádzať so zoznamom susedných miest, pretože musíme prejsť zoznamom uzlov pripojených ku každému uzlu, len čo je uzol vyradený z radu z hlavy (alebo začiatku) uzla. frontu.

Graf použitý na demonštráciu kódu bude identický s grafom použitým v predchádzajúcom príklade.

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