Menu

Program C ++ zameraný na hĺbkové hľadanie (DFS) na prechádzanie grafom alebo stromom

  • Hlavná
  • Iné
  • Program C ++ zameraný na hĺbkové hľadanie (DFS) na prechádzanie grafom alebo stromom

depth first search c program traverse graph

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento výukový program pokrýva hĺbkové prvé vyhľadávanie (DFS) v jazyku C ++, v ktorom je graf alebo strom prechádzaný hlboko. Dozviete sa tiež Algoritmus a implementácia DFS:

Vyhľadávanie hĺbky (DFS) je ďalšou technikou používanou na prechádzanie stromom alebo grafom.

DFS začína koreňovým uzlom alebo počiatočným uzlom a potom skúma susedné uzly aktuálneho uzla hlbšie do grafu alebo stromu. To znamená, že v DFS sú uzly preskúmané hĺbkovo, kým nenarazíte na uzol bez potomkov.

Akonáhle sa dosiahne listový uzol, DFS ustúpi a začne podobným spôsobom skúmať ďalšie uzly.

=> Tu si pozrite pozorne na Sprievodcu školením pre C ++.

Vyhľadávanie do hĺbky

Čo sa dozviete:

Hĺbkovo prvé vyhľadávanie (DFS) v C ++

Na rozdiel od BFS, v ktorom skúmame uzly po šírke, v DFS skúmame uzly hĺbkovo. V DFS používame štruktúru zásobníkových dát na ukladanie skúmaných uzlov. Hrany, ktoré nás vedú k nepreskúmaným uzlom, sa nazývajú „objavovacie hrany“, zatiaľ čo hrany vedúce k už navštíveným uzlom sa nazývajú „hrany blokov“.

Ďalej uvidíme algoritmus a pseudokód pre techniku ​​DFS.

Algoritmus DFS

  • Krok 1: Vložte koreňový uzol alebo počiatočný uzol stromu alebo grafu do zásobníka.
  • Krok 2: Vyberte hornú položku zo zásobníka a pridajte ju do zoznamu navštívených.
  • Krok 3: Nájdite všetky susedné uzly uzla označeného ako navštívené a pridajte tie, ktoré ešte nie sú navštívené, do stohu.
  • Krok 4 : Opakujte kroky 2 a 3, kým nie je zásobník prázdny.

Pseudokód

Pseudokód pre DFS je uvedený nižšie.

Pseudokód pre DFS

Z vyššie uvedeného pseudokódu si všimneme, že DFS algoritmus sa volá rekurzívne na každom vrchole, aby sa zabezpečilo, že sú navštívené všetky vrcholy.

Traverzy s ilustráciami

Poďme si teraz ilustrovať prechod DFS grafu. Kvôli prehľadnosti použijeme rovnaký graf, aký sme použili na ilustrácii BFS.

Ilustrácie DFS s prechodmi

Nech 0 je počiatočný uzol alebo zdrojový uzol. Najskôr ho označíme ako navštívený a pridáme do zoznamu navštívených. Potom zatlačíme všetky jeho susedné uzly v zásobníku.

Zatlačte všetky susedné uzly v zásobníku

Ďalej vezmeme jeden zo susedných uzlov na spracovanie, tj. Hornú časť stohu, ktorá je 1. Označíme ho ako navštívený pridaním do navštíveného zoznamu. Teraz vyhľadajte susedné uzly 1. Pretože 0 je už v zozname navštívených, ignorujeme to a navštevujeme 2, čo je horná časť zásobníka.

Ilustrácia DFS - krok 3

Ďalej označíme uzol 2 ako navštívený. Jeho susedný uzol 4 je pridaný do stohu.

Ilustrácia DFS, krok 4

Ďalej označíme 4, čo je horná časť zásobníka ako navštívená. Uzol 4 má ako susedný iba uzol 2, ktorý je už navštívený, a preto ho ignorujeme.

Ilustrácia DFS, krok 5

V tejto fáze je v zásobníku iba uzol 3. Jeho susedný uzol 0 je už navštívený, a preto ho ignorujeme. Teraz označíme 3 ako navštívené.

Ilustrácia DFS, krok 6

Teraz je zásobník prázdny a navštívený zoznam zobrazuje postupnosť priechodu prvého hĺbky daného grafu.

Ak sledujeme daný graf a sekvenciu prechodu, všimneme si, že pre algoritmus DFS skutočne prechádzame grafom hĺbkovo a potom ho späť sledujeme, aby sme preskúmali nové uzly.

Implementácia vyhľadávania do hĺbky

Poďme implementovať techniku ​​prechodu DFS pomocou C ++.

#include #include using namespace std; //graph class for DFS travesal class DFSGraph { int V; // No. of vertices list *adjList; // adjacency list void DFS_util(int v, bool visited()); // A function used by DFS public: // class Constructor DFSGraph(int V) { this->V = V; adjList = new list(V); } // function to add an edge to graph void addEdge(int v, int w){ adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal function }; void DFSGraph::DFS_util(int v, bool visited()) { // current node v is visited visited(v) = true; cout << v << ' '; // recursively process all the adjacent vertices of the node list::iterator i; for(i = adjList(v).begin(); i != adjList(v).end(); ++i) if(!visited(*i)) DFS_util(*i, visited); } // DFS traversal void DFSGraph::DFS() { // initially none of the vertices are visited bool *visited = new bool(V); for (int i = 0; i < V; i++) visited(i) = false; // explore the vertices one by one by recursively calling DFS_util for (int i = 0; i < V; i++) if (visited(i) == false) DFS_util(i, visited); } int main() { // Create a graph DFSGraph gdfs(5); gdfs.addEdge(0, 1); gdfs.addEdge(0, 2); gdfs.addEdge(0, 3); gdfs.addEdge(1, 2); gdfs.addEdge(2, 4); gdfs.addEdge(3, 3); gdfs.addEdge(4, 4); cout << 'Depth-first traversal for the given graph:'<

Výkon:

Traverz hĺbky pre daný graf:

0 1 2 4 3

Graf sme opäť použili v programe, ktorý sme použili na ilustračné účely. Vidíme, že DFS algoritmus (rozdelený na dve funkcie) sa volá rekurzívne na každom vrchole v grafe, aby sa zabezpečilo, že sú navštívené všetky vrcholy.

Analýza za behu

Časová zložitosť DFS je rovnaká ako BFS t.j. O (| V | + | E |) kde V je počet vrcholov a E je počet hrán v danom grafe.

Podobne ako pri BFS, v závislosti od toho, či je graf málo osídlený alebo husto osídlený, budú pri výpočte časovej zložitosti dominantným faktorom vrcholy alebo hrany.

Iteračný DFS

Vyššie uvedená implementácia pre techniku ​​DFS má rekurzívnu povahu a využíva zásobník volaní funkcií. Máme ďalšiu variáciu na implementáciu DFS, tj. „ Iteratívne hĺbkové prvé vyhľadávanie “. V tomto používame explicitný zásobník na udržanie navštívených vrcholov.

Implementáciu pre iteratívny DFS sme si ukázali nižšie. Všimnite si, že implementácia je rovnaká ako BFS, okrem faktora, že namiesto fronty používame štruktúru dát zásobníka.

#include using namespace std; // graph class class Graph { int V; // No. of vertices list *adjList; // adjacency lists public: Graph(int V) //graph Constructor { this->V = V; adjList = new list(V); } void addEdge(int v, int w) // add an edge to graph { adjList(v).push_back(w); // Add w to v’s list. } void DFS(); // DFS traversal // utility function called by DFS void DFSUtil(int s, vector &visited); }; //traverses all not visited vertices reachable from start node s void Graph::DFSUtil(int s, vector &visited) { // stack for DFS stack dfsstack; // current source node inside stack dfsstack.push(s); while (!dfsstack.empty()) { // Pop a vertex s = dfsstack.top(); dfsstack.pop(); // display the item or node only if its not visited if (!visited(s)) { cout << s << ' '; visited(s) = true; } // explore all adjacent vertices of popped vertex. //Push the vertex to the stack if still not visited for (auto i = adjList(s).begin(); i != adjList(s).end(); ++i) if (!visited(*i)) dfsstack.push(*i); } } // DFS void Graph::DFS() { // initially all vertices are not visited vector visited(V, false); for (int i = 0; i < V; i++) if (!visited(i)) DFSUtil(i, visited); } //main program int main() { Graph gidfs(5); //create graph gidfs.addEdge(0, 1); gidfs.addEdge(0, 2); gidfs.addEdge(0, 3); gidfs.addEdge(1, 2); gidfs.addEdge(2, 4); gidfs.addEdge(3, 3); gidfs.addEdge(4, 4); cout << 'Output of Iterative Depth-first traversal: '; gidfs.DFS(); return 0; }

Výkon:

Výstup iteračného priechodu hĺbkou:

0 3 2 4 1

Používame rovnaký graf, aký sme použili pri našej rekurzívnej implementácii. Rozdiel vo výstupe je ten, že zásobník používame v iteratívnej implementácii. Keď zásobníky sledujú poradie LIFO, dostaneme inú postupnosť DFS. Ak chcete získať rovnakú postupnosť, možno budeme chcieť vložiť vrcholy v opačnom poradí.

BFS vs DFS

Doteraz sme diskutovali o oboch technikách prechodu grafov, t. J. BFS a DFS.

Pozrime sa teraz na rozdiely medzi nimi.

BFSDFS
Znamená „vyhľadávanie na šírku“Znamená „vyhľadávanie do hĺbky“
Uzly sú preskúmané po šírke po jednotlivých úrovniach.Uzly sa skúmajú hĺbkovo, až kým nie sú iba listové uzly, a potom sa stiahnu späť, aby sa preskúmali ďalšie nenavštívené uzly.
BFS sa vykonáva pomocou dátovej štruktúry frontu.DFS sa vykonáva pomocou dátovej štruktúry zásobníka.
Pomalšie vo výkone.Rýchlejšie ako BFS.
Užitočné pri hľadaní najkratšej cesty medzi dvoma uzlami.Používa sa hlavne na detekciu cyklov v grafoch.

Aplikácie DFS

  • Detekcia cyklov v grafe: Ak nájdeme zadnú hranu pri vykonávaní DFS v grafe, môžeme vyvodiť záver, že graf má cyklus. Preto sa DFS používa na detekciu cyklov v grafe.
  • Hľadanie cesty: Vzhľadom na dva vrcholy x a y môžeme pomocou DFS nájsť cestu medzi x a y. Začíname vrcholom x a potom tlačíme všetky vrcholy na ceste k zásobníku, až kým nenarazíme na y. Obsah stohu udáva cestu medzi x a y.
  • Minimálny rozpätie stromu a najkratšia cesta: Prechod DFS neváženého grafu nám dáva minimálny spanningový strom a najkratšiu cestu medzi uzlami.
  • Topologické triedenie: Topologické triedenie používame, keď potrebujeme naplánovať úlohy z daných závislostí medzi úlohami. V oblasti počítačovej vedy ho väčšinou používame na riešenie závislostí symbolov v linkeroch, serializáciu údajov, plánovanie inštrukcií atď. DFS je široko používaný v topologickom triedení.

Záver

V posledných pár tutoriáloch sme preskúmali viac o dvoch technikách prechodu pre grafy, tj BFS a DFS. Videli sme rozdiely, ako aj použitie oboch techník. BFS a DFS v podstate dosahujú rovnaký výsledok pri návšteve všetkých uzlov grafu, líšia sa však poradím výstupu a spôsobom, akým sa to deje.

Videli sme tiež implementáciu oboch techník. Zatiaľ čo BFS používa rad, DFS na implementáciu tejto techniky využíva zásobníky. Týmto uzatvárame tutoriál o technikách prechodu grafov. Na stromoch môžeme tiež použiť BFS a DFS.

aký je najlepší e-mail

Dozvieme sa viac o rozpätí stromov a niekoľkých algoritmoch na nájdenie najkratšej cesty medzi uzlami grafu v našom pripravovanom výučbe.

=> Ak chcete preskúmať celý zoznam výukových programov C ++, prečítajte si tu.

Odporúčané čítanie

^