Šiame straipsnyje aptarsime BFS algoritmą duomenų struktūroje. Pirmoji paieška yra grafiko perėjimo algoritmas, kuris pradeda eiti grafiką nuo šakninio mazgo ir ištiria visus gretimus mazgus. Tada jis pasirenka artimiausią mazgą ir ištiria visus neištirtus mazgus. Naudojant BFS perėjimui, bet kuris grafiko mazgas gali būti laikomas šakniniu mazgu.
Yra daug būdų, kaip pereiti grafiką, tačiau tarp jų BFS yra dažniausiai naudojamas metodas. Tai rekursinis algoritmas, skirtas ieškoti visose medžio ar grafiko duomenų struktūros viršūnėse. BFS kiekvieną grafiko viršūnę suskirsto į dvi kategorijas – aplankytas ir nelankytas. Jis pasirenka vieną grafiko mazgą ir po to aplanko visus mazgus, esančius greta pasirinkto mazgo.
BFS algoritmo taikymai
Plotis-pirmiausia-algoritmo taikymai pateikiami taip:
- BFS gali būti naudojamas gretimoms vietoms rasti iš nurodytos šaltinio vietos.
- Lygiamajame tinkle BFS algoritmas gali būti naudojamas kaip perėjimo metodas, norint rasti visus gretimus mazgus. Dauguma „torrent“ klientų, tokių kaip „BitTorrent“, „uTorrent“ ir kt., naudoja šį procesą, norėdami tinkle rasti „sėklas“ ir „bendradarbius“.
- BFS gali būti naudojamas žiniatinklio tikrinimo programose tinklalapių indeksams kurti. Tai vienas iš pagrindinių algoritmų, kurį galima naudoti interneto puslapiams indeksuoti. Jis pradeda eiti nuo šaltinio puslapio ir seka su puslapiu susijusias nuorodas. Čia kiekvienas tinklalapis laikomas grafiko mazgu.
- BFS naudojamas trumpiausiam keliui ir mažiausiam tarpatraminiam medžiui nustatyti.
- BFS taip pat naudojamas Cheney technikoje šiukšlių surinkimui dubliuoti.
- Jis gali būti naudojamas Ford-Fulkerson metodu maksimaliam srautui srauto tinkle apskaičiuoti.
Algoritmas
Veiksmai, susiję su BFS algoritmu, norint ištirti grafiką, pateikiami taip:
1 žingsnis: NUSTATYTI STATUSĄ = 1 (parengties būsena) kiekvienam G mazgui
2 žingsnis: Įrašykite pradinį mazgą A ir nustatykite jo STATUSĄ = 2 (laukimo būsena)
3 veiksmas: Kartokite 4 ir 5 veiksmus, kol EILĖ bus tuščia
4 veiksmas: Iškelkite į eilę mazgo N. Apdorokite jį ir nustatykite jo STATUS = 3 (apdorota būsena).
5 veiksmas: Į eilę įrašykite visus N kaimynus, kurie yra parengties būsenoje (kurių STATUSAS = 1) ir nustatykite
nedeterministiniai baigtiniai automatai
jų STATUSAS = 2
(laukimo būsena)
masyvas pridedant elementus java
[KILPOS PABAIGA]
6 veiksmas: IŠĖJIMAS
BFS algoritmo pavyzdys
Dabar, naudodamiesi pavyzdžiu, supraskime BFS algoritmo veikimą. Toliau pateiktame pavyzdyje yra nukreiptas grafikas, turintis 7 viršūnes.
Aukščiau pateiktame grafike minimalų kelią „P“ galima rasti naudojant BFS, kuris prasidės nuo A mazgo ir baigsis mazge E. Algoritmas naudoja dvi eiles, būtent QUEUE1 ir QUEUE2. QUEUE1 turi visus mazgus, kurie turi būti apdoroti, o QUEUE2 - visus mazgus, kurie yra apdoroti ir ištrinti iš QUEUE1.
Dabar pradėkime nagrinėti grafiką, pradedant nuo mazgo A.
1 žingsnis - Pirmiausia pridėkite A prie 1 eilės ir NULL prie 2 eilės.
QUEUE1 = {A} QUEUE2 = {NULL} 2 žingsnis - Dabar ištrinkite A mazgą iš 1 eilės ir pridėkite jį prie 2 eilės. Į eilę1 įterpkite visus mazgo A kaimynus.
QUEUE1 = {B, D} QUEUE2 = {A} 3 veiksmas - Dabar ištrinkite B mazgą iš 1 eilės ir pridėkite jį prie 2 eilės. Į eilę1 įterpkite visus mazgo B kaimynus.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} 4 veiksmas - Dabar ištrinkite mazgą D iš eilės1 ir pridėkite jį prie 2 eilės. Į eilę1 įterpkite visus mazgo D kaimynus. Vienintelis mazgo D kaimynas yra F, nes jis jau įdėtas, todėl jis nebus įdėtas dar kartą.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} 5 veiksmas - Ištrinkite mazgą C iš eilės1 ir įtraukite jį į eilę2. Į eilę1 įterpkite visus mazgo C kaimynus.
pirminio rakto sudėtinis raktas
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} 5 veiksmas - Ištrinkite mazgą F iš eilės1 ir įtraukite jį į eilę2. Į eilę1 įterpkite visus mazgo F kaimynus. Kadangi visi mazgo F kaimynai jau yra, daugiau jų neįterpsime.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} 6 veiksmas - Ištrinkite mazgą E iš eilės1. Kadangi visi jo kaimynai jau pridėti, todėl daugiau jų neįterpsime. Dabar aplankomi visi mazgai, o tikslinis mazgas E patenka į eilę2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} BFS algoritmo sudėtingumas
BFS laiko sudėtingumas priklauso nuo duomenų struktūros, naudojamos diagramai pavaizduoti. BFS algoritmo laiko sudėtingumas yra O (V+E) , nes blogiausiu atveju BFS algoritmas tiria kiekvieną mazgą ir kraštą. Grafe viršūnių skaičius yra O(V), o briaunų skaičius yra O(E).
BFS erdvės sudėtingumą galima išreikšti kaip O(V) , kur V yra viršūnių skaičius.
BFS algoritmo įgyvendinimas
Dabar pažiūrėkime, kaip įdiegtas BFS algoritmas Java.
Šiame kode mes naudojame gretimų vietų sąrašą, kad pavaizduotume savo diagramą. „Java“ įdiegus „Breadth-First Search“ algoritmą, daug lengviau tvarkyti gretimų vietų sąrašą, nes prie kiekvieno mazgo prijungtų mazgų sąrašą turime pereiti tik tada, kai mazgas pašalinamas iš eilės pradžios (arba pradžios).
Šiame pavyzdyje grafikas, kurį naudojame kodui parodyti, pateikiamas taip:
import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; 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[vertex]; 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(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that's all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>