Kas yra BFS?
Breadth-First Search (BFS) yra pagrįsta perėjimo mazgais, įtraukiant kiekvieno mazgo kaimynus į eilę, pradedant nuo šakninio mazgo. Grafo BFS yra panašus į medžio BFS, išskyrus tai, kad grafikai gali turėti ciklus. Priešingai nei atliekant paiešką pagal gylį, visi kaimyniniai mazgai tam tikrame gylyje yra tiriami prieš pereinant į kitą lygį.
BFS algoritmas
Toliau pateikiami žingsniai, susiję su plačios paieškos naudojimu grafiko tyrinėjimui:
- Paimkite grafiko gretimų matricos arba gretimų sąrašo duomenis.
- Sukurkite eilę ir užpildykite ją elementais.
- Suaktyvinkite šakninį mazgą (tai reiškia, kad šakninis mazgas būtų gaunamas eilės pradžioje).
- Ištraukite eilės pavadinimą (arba pradinį elementą), tada į eilę įtraukite visus šalia esančius eilės mazgus iš kairės į dešinę. Tiesiog pašalinkite galvutę ir tęskite operaciją, jei mazgas neturi netoliese esančių mazgų, kuriuos reikia ištirti. (Pastaba: jei atsiranda kaimynas, kuris anksčiau buvo ištirtas arba yra eilėje, nedėkite jo į eilę, o praleiskite.)
- Tęskite taip, kol eilė bus tuščia.
BFS programos
Dėl algoritmo lankstumo „Breadth-First Search“ yra gana naudinga realiame pasaulyje. Štai keletas iš jų:
- Peer-to-peer tinkle aptinkami peer mazgai. Dauguma „torrent“ klientų, tokių kaip „BitTorrent“, „uTorrent“ ir „qBittorent“, naudoja šį procesą, norėdami tinkle rasti „sėklas“ ir „bendradarbius“.
- Indeksas sukurtas naudojant žiniatinklio tikrinimo grafiko perėjimo metodus. Procedūra prasideda nuo šaltinio puslapio kaip šakninio mazgo ir tęsiasi iki visų antrinių puslapių, susietų su šaltinio puslapiu (ir šis procesas tęsiasi). Dėl sumažėjusio rekursijos medžio gylio „Breadth-First Search“ čia turi būdingą pranašumą.
- Naudodami GPS navigacijos sistemas, naudodami GPS, atlikite paiešką, kad surastumėte netoliese esančias svetaines.
- Cheney technika, kurioje naudojama paieškos pagal plotį koncepcija, naudojama šiukšlėms rinkti.
BFS traversal pavyzdys
Norėdami pradėti, pažvelkime į paprastą pavyzdį. Pradėsime nuo 0 kaip šakninio mazgo ir eisime žemyn diagrama.
eilutė prieš stulpelį
1 žingsnis: Eilė (0)
Eilė
| 0 |
2 žingsnis: Eilė (0), eilė (1), eilė (3), eilė (4)
Eilė
| 1 | 3 | 4 |
3 veiksmas: Eilė (1), eilė (2)
java eilutę char
Eilė
| 3 | 4 | 2 |
4 veiksmas: Eilė (3), eilė (5). 1 į eilę dar kartą nepridėsime, nes 0 jau buvo ištirta.
Eilė
| 4 | 2 | 5 |
5 veiksmas: Nutraukti į eilę (4)
Eilė
python eilutė surūšiuota
| 2 | 5 |
6 veiksmas: Nutraukti į eilę (2)
Eilė
java daryti kol
| 5 |
7 veiksmas: Nutraukti į eilę (5)
Eilė
Eilė dabar tuščia, todėl procesą sustabdysime.
„Java“ programa „Breadth-First Search“.
Yra keletas būdų, kaip elgtis su kodu. Dažniausiai aptarsime veiksmus, susijusius su pirmosios plačios paieškos „Java“ diegimu. Grafams saugoti galima naudoti gretimų vietų sąrašą arba gretimų matricą; bet kuris metodas yra priimtinas. Gretimų sąrašas bus naudojamas mūsų grafikai mūsų kode pavaizduoti. Diegiant „Breadth-First Search“ algoritmą „Java“, daug lengviau susidoroti su gretimų sąrašu, nes turime pereiti prie kiekvieno mazgo prijungtų mazgų sąrašą tik tada, kai mazgas pašalinamas iš eilės (arba pradžios). eilė.
Grafikas, naudojamas kodui parodyti, bus toks pat, kaip ir ankstesniame pavyzdyje.
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;>