Co je BFS?

BFS (Breadth-First Search) je založeno na procházení uzlů přidáním sousedů každého uzlu do fronty procházení počínaje kořenovým uzlem. BFS pro graf je podobný jako u stromu s tou výjimkou, že grafy mohou mít cykly. Na rozdíl od prohledávání do hloubky jsou všechny sousední uzly v dané hloubce prozkoumány před pokračováním na další úroveň.

Algoritmus BFS

Níže jsou uvedeny kroky, které se týkají použití prohledávání do šířky k prozkoumání grafu:

1. Vezměte data pro matici sousedství nebo seznam sousedství grafu.
2. Vytvořte frontu a naplňte ji položkami.
3. Aktivujte kořenový uzel (to znamená, že dostanete kořenový uzel na začátek fronty).
4. Zařaďte do fronty hlavu (nebo počáteční prvek) a poté zařaďte všechny blízké uzly fronty zleva doprava. Jednoduše vyřaďte hlavu a pokračujte v operaci, pokud uzel nemá žádné blízké uzly, které je třeba prozkoumat. (Poznámka: Pokud se objeví soused, který byl dříve vyšetřován nebo je ve frontě, nezařazujte jej do fronty, místo toho jej přeskočte.)
5. Pokračujte tímto způsobem, dokud není fronta prázdná.

Aplikace BFS

Díky flexibilitě algoritmu je vyhledávání Breadth-First docela užitečné v reálném světě. Toto jsou některé z nich:

1. V síti peer-to-peer jsou objeveny uzly peer. Většina torrent klientů, jako je BitTorrent, uTorrent a qBittorent, využívá tento proces k nalezení „semen“ a „rovníků“ v síti.
2. Index je vytvořen pomocí technik procházení grafů při procházení webu. Procedura začíná zdrojovou stránkou jako kořenovým uzlem a postupuje dolů ke všem sekundárním stránkám, které jsou propojeny se zdrojovou stránkou (a tento proces pokračuje). Díky snížené hloubce rekurzního stromu má zde Breadth-First Search neodmyslitelnou výhodu.
3. Pomocí navigačních systémů GPS využívajících GPS proveďte nejprve prohledávání do šířky, abyste našli místa v okolí.
4. Ke sběru odpadků se používá Cheneyho technika, která využívá koncept prohledávání do šířky.

Příklad BFS Traversal

Pro začátek se podívejme na jednoduchý příklad. Začneme s 0 jako kořenovým uzlem a postupujeme v grafu dolů.

ostrov java

Krok 1: Zařadit (0)

Fronta

Krok 2: Zařadit do fronty (0), Zařadit do fronty (1), Zařadit do fronty (3), Zařadit do fronty (4)

Fronta

Krok 3: Dequeue(1), Enqueue (2)

jak převést z int na řetězec v java

Fronta

Krok 4: Dequeue(3), Enqueue(5). 1 do fronty znovu nepřidáme, protože 0 již byla prozkoumána.

Fronta

Krok 5: Dequeue (4)

Fronta

přidat do pole java

Krok 6: Dequeue (2)

Fronta

jak třídit arraylist v Javě

Krok 7: Dequeue (5)

Fronta

Fronta je nyní prázdná, takže proces zastavíme.

Program Java pro vyhledávání na prvním místě

Existuje několik přístupů, jak nakládat s kódem. Budeme většinou diskutovat o krocích při implementaci plošného vyhledávání v Javě. Pro ukládání grafů lze použít seznam sousedství nebo matici sousedství; kterýkoli způsob je přijatelný. Seznam sousedství bude použit k reprezentaci našeho grafu v našem kódu. Při implementaci algoritmu Breadth-First Search v Javě je mnohem snazší vypořádat se se seznamem sousedství, protože musíme pouze procházet seznam uzlů připojených ke každému uzlu, jakmile je uzel vyřazen z fronty z hlavy (nebo začátku) uzlu. fronta.

Graf použitý k demonstraci kódu bude identický s grafem použitým v předchozím příkladu.

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