Mi az a BFS?

A Breadth-First Search (BFS) a csomópontok bejárásán alapul, azáltal, hogy az egyes csomópontok szomszédjait hozzáadja a bejárási sorhoz a gyökércsomóponttól kezdve. A gráf BFS-e hasonló a fához, azzal az eltéréssel, hogy a gráfoknak lehetnek ciklusai. A mélységi kereséssel ellentétben egy adott mélységben minden szomszédos csomópontot megvizsgálunk, mielőtt a következő szintre lépnénk.

BFS algoritmus

A következő lépések szükségesek a szélesség-első keresés használatához a grafikonok felfedezéséhez:

karakterlánc a jsonobjecthez

1. Vegyük az adatokat a gráf szomszédsági mátrixához vagy szomszédsági listájához.
2. Hozzon létre egy sort, és töltse fel elemekkel.
3. Aktiválja a gyökércsomópontot (ami azt jelenti, hogy a gyökércsomópontot a sor elején kapja meg).
4. Állítsa sorba a sor fejét (vagy kezdeti elemét), majd helyezze sorba a sor összes közeli csomópontját balról jobbra. Egyszerűen állítsa ki a fejet a sorból, és folytassa a műveletet, ha egy csomópontnak nincsenek közeli csomópontjai, amelyeket ki kell vizsgálni. (Megjegyzés: Ha olyan szomszéd kerül elő, amelyet korábban megvizsgáltak, vagy amely a sorban áll, ne helyezze sorba, hanem hagyja ki.)
5. Folytassa így, amíg a sor ki nem ürül.

BFS alkalmazások

Az algoritmus rugalmassága miatt a Breadth-First Search igen hasznos a való világban. Ezek közül néhány:

1. Egy peer-to-peer hálózatban peer csomópontokat fedez fel. A legtöbb torrent kliens, mint például a BitTorrent, az uTorrent és a qBittorent, ezt a folyamatot alkalmazza „magok” és „társak” megtalálására a hálózatban.
2. Az index a webes feltérképezés során alkalmazott gráfbejárási technikák felhasználásával készült. Az eljárás a forrásoldallal kezdődik, mint gyökércsomóponttal, és lefelé halad az összes másodlagos oldalra, amely a forrásoldalhoz kapcsolódik (és ez a folyamat folytatódik). A rekurziós fa csökkentett mélysége miatt a Breadth-First Search itt rejlő előnyökkel rendelkezik.
3. A GPS-t használó GPS-navigációs rendszerek használata széleskörű keresést végez a közeli helyek megtalálásához.
4. Cheney technikáját, amely a szélesség-első keresés koncepcióját alkalmazza, a szemétgyűjtésre használják.

Példa BFS-bejárásra

A kezdéshez nézzünk egy egyszerű példát. Kezdjük 0-val, mint gyökércsomóponttal, és lefelé haladunk a grafikonon.

1. lépés: sor(0)

Sor

2. lépés: Sor (0), sor (1), sor (3), sor (4)

Sor

3. lépés: Sorból (1), sorba (2)

Sor

4. lépés: Dequeue (3), sorba (5). Nem adunk újra 1-et a sorhoz, mert a 0-t már feltártuk.

Sor

5. lépés: Sorból (4)

string int konvertálása java-ban

Sor

6. lépés: Sorból (2)

Sor

7. lépés: Sorból (5)

Sor

A sor most üres, ezért leállítjuk a folyamatot.

Breadth-First Search Java program

Számos megközelítés létezik a kóddal való kezelésre. Leginkább a széleskörű keresés Java nyelven történő megvalósításának lépéseit tárgyaljuk. Grafikonok tárolására szomszédsági lista vagy szomszédsági mátrix használható; bármelyik módszer elfogadható. A szomszédsági lista fogja használni a gráfunkat a kódunkban. A Breadth-First Search algoritmus Java nyelven való implementálásakor sokkal könnyebb kezelni a szomszédsági listát, mivel csak akkor kell végighaladnunk az egyes csomópontokhoz csatolt csomópontok listáján, ha a csomópont kikerül a sorból a csomópont elejétől (vagy elejétől). sorban.

A kód bemutatására használt grafikon megegyezik az előző példában használt grafikonnal.

stdin a c

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