V tomto článku budeme diskutovat o algoritmu BFS v datové struktuře. Prohledávání do šířky je algoritmus procházení grafu, který začíná procházet grafem od kořenového uzlu a prozkoumává všechny sousední uzly. Poté vybere nejbližší uzel a prozkoumá všechny neprozkoumané uzly. Při použití BFS pro procházení lze jakýkoli uzel v grafu považovat za kořenový uzel.
Existuje mnoho způsobů, jak procházet grafem, ale mezi nimi je BFS nejčastěji používaným přístupem. Jedná se o rekurzivní algoritmus pro prohledávání všech vrcholů stromové nebo grafové datové struktury. BFS rozděluje každý vrchol grafu do dvou kategorií – navštívené a nenavštívené. Vybere jeden uzel v grafu a poté navštíví všechny uzly sousedící s vybraným uzlem.
Aplikace algoritmu BFS
Aplikace algoritmu do šířky jsou uvedeny následovně -
- BFS lze použít k nalezení sousedních míst z daného zdrojového místa.
- V síti peer-to-peer lze algoritmus BFS použít jako metodu procházení k nalezení všech sousedních uzlů. Většina torrentových klientů, jako je BitTorrent, uTorrent atd., využívá tento proces k nalezení „seed“ a „peers“ v síti.
- BFS lze použít ve webových prohledávačích k vytváření indexů webových stránek. Je to jeden z hlavních algoritmů, které lze použít k indexování webových stránek. Začne procházet ze zdrojové stránky a následuje odkazy spojené se stránkou. Zde je každá webová stránka považována za uzel v grafu.
- BFS se používá k určení nejkratší cesty a minimální kostry.
- BFS se také používá v Cheneyho technice k duplikování sběru odpadu.
- Může být použit ve ford-Fulkersonově metodě k výpočtu maximálního průtoku v průtokové síti.
Algoritmus
Kroky zahrnuté v algoritmu BFS k prozkoumání grafu jsou uvedeny následovně -
Krok 1: SET STATUS = 1 (stav připravenosti) pro každý uzel v G
Krok 2: Zařaďte počáteční uzel A a nastavte jeho STATUS = 2 (stav čekání)
Krok 3: Opakujte kroky 4 a 5, dokud nebude FRONTA prázdná
Krok 4: Zařaďte uzel N do fronty. Zpracujte jej a nastavte jeho STAV = 3 (stav zpracování).
Krok 5: Zařaďte do fronty všechny sousedy N, kteří jsou ve stavu připravenosti (jejichž STATUS = 1) a nastavte
abeceda jako čísla
jejich STAV = 2
(stav čekání)
scan.nextstring java
[KONEC SMYČKY]
Krok 6: VÝSTUP
Příklad algoritmu BFS
Nyní pochopme fungování algoritmu BFS pomocí příkladu. V níže uvedeném příkladu je orientovaný graf se 7 vrcholy.
Ve výše uvedeném grafu lze minimální cestu 'P' nalézt pomocí BFS, která bude začínat v uzlu A a končit v uzlu E. Algoritmus používá dvě fronty, jmenovitě QUEUE1 a QUEUE2. QUEUE1 obsahuje všechny uzly, které mají být zpracovány, zatímco QUEUE2 obsahuje všechny uzly, které jsou zpracovány a odstraněny z QUEUE1.
Nyní začněme zkoumat graf od uzlu A.
Krok 1 - Nejprve přidejte A do queue1 a NULL do queue2.
QUEUE1 = {A} QUEUE2 = {NULL} Krok 2 - Nyní odstraňte uzel A z fronty1 a přidejte jej do fronty2. Vložte všechny sousedy uzlu A do fronty1.
QUEUE1 = {B, D} QUEUE2 = {A} Krok 3 - Nyní odstraňte uzel B z fronty1 a přidejte jej do fronty2. Vložte všechny sousedy uzlu B do fronty1.
QUEUE1 = {D, C, F} QUEUE2 = {A, B} Krok 4 - Nyní odstraňte uzel D z fronty1 a přidejte jej do fronty2. Vložte všechny sousedy uzlu D do fronty1. Jediným sousedem uzlu D je F, protože je již vložen, takže nebude znovu vložen.
QUEUE1 = {C, F} QUEUE2 = {A, B, D} Krok 5 - Odstraňte uzel C z fronty1 a přidejte jej do fronty2. Vložte všechny sousedy uzlu C do fronty1.
javascriptový víceřádkový řetězec
QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} Krok 5 - Odstraňte uzel F z fronty1 a přidejte jej do fronty2. Vložte všechny sousedy uzlu F do fronty1. Protože všichni sousedé uzlu F jsou již přítomni, nebudeme je znovu vkládat.
QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} Krok 6 - Odstranit uzel E z fronty1. Vzhledem k tomu, že všichni jeho sousedé již byli přidáni, nebudeme je znovu vkládat. Nyní jsou navštíveny všechny uzly a cílový uzel E je nalezen ve frontě2.
QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} Složitost algoritmu BFS
Časová složitost BFS závisí na datové struktuře použité k reprezentaci grafu. Časová složitost algoritmu BFS je O(V+E) , protože v nejhorším případě algoritmus BFS prozkoumá každý uzel a hranu. V grafu je počet vrcholů O(V), zatímco počet hran je O(E).
Prostorová složitost BFS může být vyjádřena jako O(V) , kde V je počet vrcholů.
Implementace algoritmu BFS
Nyní se podívejme na implementaci algoritmu BFS v jazyce Java.
V tomto kódu používáme k reprezentaci našeho grafu seznam sousedství. Implementace algoritmu Breadth-First Search v Javě výrazně usnadňuje práci se seznamem sousedství, protože musíme procházet seznam uzlů připojených ke každému uzlu, jakmile je uzel vyřazen z fronty (neboli začátek) fronty.
V tomto příkladu je graf, který používáme k demonstraci kódu, uveden následovně -
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;>