breadth first search c program traverse graph
Tento výukový program obsahuje prvé šírkové hľadanie v jazyku C ++, v ktorom je graf alebo strom prechádzaný po celej šírke. Dozviete sa tiež Algoritmus a implementácia BFS:
Tento explicitný tutoriál v C ++ vám poskytne podrobné vysvetlenie techník prechodu, ktoré je možné vykonať na strome alebo grafe.
Traversal je technika, pomocou ktorej navštevujeme každý uzol grafu alebo stromu. Existujú dva štandardné spôsoby prechodu.
- Šírka prvého vyhľadávania (BFS)
- Vyhľadávanie do hĺbky (DFS)
=> Ak chcete preskúmať celý zoznam výukových programov C ++, prečítajte si tu.
otestujte web v rôznych prehliadačoch zadarmo
Čo sa dozviete:
Technika šírky prvého vyhľadávania (BFS) v C ++
V tomto výučbe sa budeme podrobne zaoberať technikou vyhľadávania na šírku.
Pri technike prechodu na šírku sa graf alebo strom prechádza po celej šírke. Táto technika využíva dátovú štruktúru frontu na ukladanie vrcholov alebo uzlov a tiež na určenie, ktorý vrchol / uzol by sa mal prijať ďalej.
Algoritmus pre šírku začína od koreňového uzla a potom prechádza cez všetky susedné uzly. Potom vyberie najbližší uzol a preskúma všetky ostatné nenavštívené uzly. Tento proces sa opakuje, kým nebudú preskúmané všetky uzly v grafe.
Algoritmus vyhľadávania na šírku
Ďalej je uvedený algoritmus pre techniku BFS.
Zvážte G ako graf, ktorý budeme prechádzať pomocou algoritmu BFS.
Nech S je koreňový / východiskový uzol grafu.
- Krok 1: Začnite uzlom S a zaraďte ho do poradia.
- Krok 2: Nasledujúce kroky opakujte pre všetky uzly v grafe.
- Krok 3: Dequeue S a spracujte to.
- Krok 4: Zaradte do radu všetky susedné uzly S a spracujte ich.
- (END OF LOOP)
- Krok 6: VÝCHOD
Pseudokód
Pseudokód pre techniku BFS je uvedený nižšie.
Procedure BFS (G, s) G is the graph and s is the source node begin let q be queue to store nodes q.enqueue(s) //insert source node in the queue mark s as visited. while (q is not empty) //remove the element from the queue whose adjacent nodes are to be processed n = q.dequeue( ) //processing all the adjacent nodes of n for all neighbors m of n in Graph G if w is not visited q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes mark m as visited. end
Traverzy s ilustráciami
Nech 0 je počiatočný uzol alebo zdrojový uzol. Najskôr ho zaradíme do poradia v navštívenej fronte a do všetkých jej susedných uzlov vo fronte.
Ďalej vezmeme jeden zo susedných uzlov na spracovanie, tj. 1. Označíme ho ako navštívený odstránením z frontu a jeho susedné uzly umiestnime do frontu (2 a 3 už vo fronte). Pretože 0 je už navštívená, ignorujeme ju.
ako spustiť .swf
Ďalej vyradíme z uzla 2 poradie a označíme ho ako navštívený. Potom sa jeho susedný uzol 4 pridá do frontu.
Ďalej z frontu vyradíme 3 a označíme ich ako navštívené. Uzol 3 má iba jeden susedný uzol, t. J. 0, ktorý je už navštívený. Preto to ignorujeme.
V tejto fáze je vo fronte prítomný iba uzol 4. Jeho susedný uzol 2 je už navštívený, a preto ho ignorujeme. Teraz označíme 4 ako navštívené.
Ďalej je sekvenciou prítomnou v navštívenom zozname šírka prvého prechodu daného grafu.
Ak sledujeme daný graf a postupnosť prechodu, môžeme si všimnúť, že pre algoritmus BFS skutočne prechádzame grafom po šírke a potom prechádzame na ďalšiu úroveň.
Implementácia BFS
#include #include using namespace std; // a directed graph class class DiGraph { int V; // No. of vertices // Pointer to an array containing adjacency lists list *adjList; public: DiGraph(int V); // Constructor // add an edge from vertex v to w void addEdge(int v, int w); // BFS traversal sequence starting with s ->starting node void BFS(int s); }; DiGraph::DiGraph(int V) { this->V = V; adjList = new list (V); } void DiGraph::addEdge(int v, int w) { adjList(v).push_back(w); // Add w to v’s list. } void DiGraph::BFS(int s) { // initially none of the vertices is visited bool *visited = new bool(V); for(int i = 0; i queue; // Mark the current node as visited and enqueue it visited(s) = true; queue.push_back(s); // iterator 'i' to get all adjacent vertices list ::iterator i; while(!queue.empty()) { // dequeue the vertex s = queue.front(); cout << s << ' '; queue.pop_front(); // get all adjacent vertices of popped vertex and process each if not already visited for (i = adjList(s).begin(); i != adjList(s).end(); ++i) { if (!visited(*i)) { visited(*i) = true; queue.push_back(*i); } } } } // main program int main() { // create a graph DiGraph dg(5); dg.addEdge(0, 1); dg.addEdge(0, 2); dg.addEdge(0, 3); dg.addEdge(1, 2); dg.addEdge(2, 4); dg.addEdge(3, 3); dg.addEdge(4, 4); cout << 'Breadth First Traversal for given graph (with 0 as starting node): '< Výkon:
bezplatný softvér na prevod videa pre Windows 10
Traverz šírky prvého pre daný graf (s 0 ako počiatočným uzlom):
0 1 2 3 4
Vo vyššie uvedenom programe sme implementovali BFS. Všimnite si, že graf je vo forme zoznamu susednosti a potom pomocou iterátora prechádzame zoznamom a vykonávame BFS.
Použili sme rovnaký graf, ktorý sme použili na ilustračné účely, ako vstup do programu na porovnanie sekvencie prechodu.
Analýza za behu
Ak V je počet vrcholov a E je počet hrán grafu, potom je možné časovú zložitosť pre BFS vyjadriť ako O (| V | + | E |) . Po tomto však záleží aj na dátovej štruktúre, ktorú používame na znázornenie grafu.
Ak použijeme zoznam susednosti (ako v našej implementácii), potom je časová zložitosť O (| V | + | E |).
Ak použijeme maticu susednosti, potom je časová zložitosť O (V ^ 2) .
Okrem použitých dátových štruktúr existuje aj skutočnosť, či je graf husto alebo riedko osídlený.
Keď počet vrcholov prekročí počet hrán, potom sa hovorí, že graf je riedko spojený, pretože bude veľa odpojených vrcholov. V tomto prípade bude časová zložitosť grafu O (V).
Na druhej strane niekedy môže mať graf vyšší počet hrán ako počet vrcholov. V takom prípade sa hovorí, že graf je husto osídlený. Časová zložitosť takého grafu je O (E).
Na záver, čo znamená výraz O (| V | + | E |), závisí od toho, či je graf husto alebo riedko osídlený, dominujúci faktor, tj. Hrany alebo vrcholy, zodpovedajúcim spôsobom určí časovú zložitosť grafu.
Aplikácie BFS Traversal
- Zber odpadu: Technika zberu odpadu, „Cheneyov algoritmus“, využíva na kopírovanie zberu odpadu prvý priechod.
- Vysielanie v sieťach: Paket putuje z jedného uzla do druhého pomocou techniky BFS vo vysielacej sieti, aby sa dostal do všetkých uzlov.
- GPS navigácia: Môžeme použiť BFS v GPS navigácii na nájdenie všetkých susedných alebo susedných lokalizačných uzlov.
- Webové stránky sociálnych sietí: Daný človek „P“, môžeme nájsť všetkých ľudí na diaľku, „d“ od p pomocou BFS až do úrovní d.
- Siete Peer to Peer: BFS možno opäť použiť v sieťach peer to peer na nájdenie všetkých susedných uzlov.
- Najkratšia cesta a strom minimálneho rozsahu v neváženom grafe: Na nájdenie najkratšej cesty, t. J. Cesty s najmenším počtom hrán v neváženom grafe, sa používa technika BFS. Podobne môžeme nájsť aj minimálny rozpätie stromu pomocou BFS v neváženom grafe.
Záver
Technika hľadania na šírku je metóda, ktorá sa používa na priechodné uzly grafu alebo stromu po šírke.
Táto technika sa väčšinou používa na nájdenie najkratšej cesty medzi uzlami grafu alebo v aplikáciách, ktoré od nás vyžadujú, aby sme navštívili každý susedný uzol, napríklad v sieťach.
=> Kliknutím sem získate bezplatný kurz C ++.
Odporúčané čítanie
- Binárny vyhľadávací strom C ++: implementácia a operácie BST s príkladmi
- Dátová štruktúra stromu B a stromu B + v C ++
- Implementácia grafov v C ++ pomocou zoznamu susedov
- Štruktúra dát binárneho stromu v C ++
- 12 najlepších nástrojov na tvorbu čiarových grafov na vytváranie úžasných čiarových grafov (2021 HODNOTENIA)
- Dátová štruktúra stromu a haldy AVL v C ++
- Stromy v C ++: Základná terminológia, techniky prechodu a typy stromov v C ++
- Graf príčin a následkov - dynamická metóda zápisu testovacích prípadov pre maximálne pokrytie s menším počtom testovacích prípadov