Menu

Program C ++ pro hloubkové vyhledávání (DFS) pro procházení grafem nebo stromem

  • Hlavní
  • Jiný
  • Program C ++ pro hloubkové vyhledávání (DFS) pro procházení grafem nebo stromem

depth first search c program traverse graph

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Tento výukový program pokrývá hloubkové první vyhledávání (DFS) v C ++, ve kterém je graf nebo strom procházen hloubkově. Dozvíte se také Algoritmus a implementace DFS:

Hledání hloubky (DFS) je další technika používaná k procházení stromu nebo grafu.

DFS začíná kořenovým uzlem nebo počátečním uzlem a poté prozkoumá sousední uzly aktuálního uzlu hlouběji do grafu nebo stromu. To znamená, že v DFS jsou uzly prozkoumány hloubkově, dokud nenarazí na uzel bez podřízených.

Jakmile je dosaženo uzlu listu, DFS ustoupí a začne zkoumat další uzly podobným způsobem.

=> Zde si všimněte výcvikového průvodce pro začátečníky v C ++.

Hledání do hloubky

Co se naučíte:

Hloubkové první vyhledávání (DFS) v C ++

Na rozdíl od BFS, ve kterém prozkoumáváme uzly po šířce, v DFS prozkoumáváme uzly hloubkově. V DFS používáme strukturu dat zásobníku pro ukládání zkoumaných uzlů. Hrany, které nás vedou k neprozkoumaným uzlům, se nazývají „objevovací hrany“, zatímco hrany vedoucí k již navštíveným uzlům se nazývají „hrany bloků“.

Dále uvidíme algoritmus a pseudokód pro techniku ​​DFS.

Algoritmus DFS

  • Krok 1: Vložte kořenový uzel nebo počáteční uzel stromu nebo grafu do zásobníku.
  • Krok 2: Vysuňte horní položku ze zásobníku a přidejte ji do navštíveného seznamu.
  • Krok 3: Najděte všechny sousední uzly uzlu označeného jako navštívené a do zásobníku přidejte ty, které ještě nejsou navštíveny.
  • Krok 4 : Opakujte kroky 2 a 3, dokud není zásobník prázdný.

Pseudo kód

Pseudokód pro DFS je uveden níže.

Pseudokód pro DFS

Z výše uvedeného pseudokódu si všimneme, že algoritmus DFS je volán rekurzivně na každém vrcholu, aby bylo zajištěno, že jsou navštíveny všechny vrcholy.

Traverzy s ilustracemi

Pojďme si nyní ilustrovat přechod DFS grafu. Pro přehlednost použijeme stejný graf, který jsme použili na ilustraci BFS.

DFS ilustrace s traverzami

Nechť 0 je počáteční uzel nebo zdrojový uzel. Nejprve ji označíme jako navštívenou a přidáme ji do seznamu navštívených. Poté zatlačíme všechny jeho přilehlé uzly v zásobníku.

Zatlačte všechny sousední uzly v zásobníku

Dále vezmeme jeden ze sousedních uzlů ke zpracování, tj. Vrchol zásobníku, který je 1. Označíme jej jako navštívený přidáním do navštíveného seznamu. Nyní vyhledejte sousední uzly 1. Protože 0 je již v navštíveném seznamu, ignorujeme to a navštěvujeme 2, což je horní část zásobníku.

Ilustrace DFS - krok 3

Dále označíme uzel 2 jako navštívený. Jeho sousední uzel 4 je přidán do zásobníku.

Ilustrace DFS Krok 4

Dále označíme 4, což je horní část zásobníku jako navštívená. Uzel 4 má jako sousední pouze uzel 2, který je již navštíven, a proto ho ignorujeme.

Ilustrace DFS Krok 5

V této fázi je v zásobníku přítomen pouze uzel 3. Jeho sousední uzel 0 je již navštíven, a proto ho ignorujeme. Nyní označíme 3 jako navštívené.

Ilustrace DFS Krok 6

Nyní je zásobník prázdný a navštívený seznam zobrazuje sekvenci průchodu první hloubky daného grafu.

Pokud sledujeme daný graf a sekvenci procházení, všimneme si, že pro algoritmus DFS skutečně procházíme grafem hloubkově a poté jej zpětně zkoumáme, abychom prozkoumali nové uzly.

Implementace vyhledávání do hloubky

Pojďme implementovat techniku ​​procházení DFS pomocí 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ýstup:

Traverz hloubky pro daný graf:

0 1 2 4 3

Opět jsme použili graf v programu, který jsme použili pro ilustrační účely. Vidíme, že DFS algoritmus (rozdělený na dvě funkce) je volán rekurzivně na každém vrcholu v grafu, aby bylo zajištěno, že jsou navštíveny všechny vrcholy.

Analýza za běhu

Časová složitost DFS je stejná jako BFS, tj. O (| V | + | E |) kde V je počet vrcholů a E je počet hran v daném grafu.

Podobně jako BFS, v závislosti na tom, zda je graf málo osídlený nebo hustě osídlený, budou dominantním faktorem při výpočtu časové složitosti vrcholy nebo hrany.

Iterativní DFS

Implementace uvedená výše pro techniku ​​DFS má rekurzivní povahu a používá zásobník volání funkcí. Máme další variantu pro implementaci DFS, tj. „ Iterativní hloubkové vyhledávání “. V tomto používáme explicitní zásobník k udržení navštívených vrcholů.

Níže jsme ukázali implementaci pro iterativní DFS. Všimněte si, že implementace je stejná jako BFS, kromě faktoru, který namísto fronty používáme datovou strukturu zásobníku.

#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ýstup:

Výstup iteračního přechodu do hloubky:

0 3 2 4 1

Používáme stejný graf, který jsme použili v naší rekurzivní implementaci. Rozdíl ve výstupu je ten, že zásobník používáme v iterativní implementaci. Vzhledem k tomu, že hromádky sledují pořadí LIFO, získáme jinou sekvenci DFS. Abychom získali stejnou sekvenci, možná bychom chtěli vložit vrcholy v opačném pořadí.

BFS vs DFS

Zatím jsme diskutovali o obou technikách procházení grafů, tj. BFS a DFS.

Nyní se podívejme na rozdíly mezi těmito dvěma.

BFSDFS
Znamená „vyhledávání na šířku“Znamená „vyhledávání do hloubky“
Uzly jsou prozkoumávány po jednotlivých úrovních.Uzly jsou prozkoumávány hloubkově, dokud nejsou pouze uzly listů, a poté jsou zpětně prozkoumány další nenavštívené uzly.
BFS se provádí pomocí datové struktury fronty.DFS se provádí pomocí datové struktury zásobníku.
Pomalejší výkon.Rychlejší než BFS.
Užitečné při hledání nejkratší cesty mezi dvěma uzly.Používá se většinou k detekci cyklů v grafech.

Aplikace DFS

  • Detekce cyklů v grafu: Pokud při provádění DFS v grafu najdeme zadní hranu, můžeme dojít k závěru, že graf má cyklus. Proto se DFS používá k detekci cyklů v grafu.
  • Hledání cesty: Vzhledem k dvěma vrcholům x a y můžeme pomocí DFS najít cestu mezi x a y. Začínáme s vrcholem x a poté tlačíme všechny vrcholy na cestě k zásobníku, dokud nenarazíme na y. Obsah zásobníku udává cestu mezi x a y.
  • Minimální rozpětí stromu a nejkratší cesta: DFS traversal neváženého grafu nám dává minimální kostru a nejkratší cestu mezi uzly.
  • Topologické třídění: Topologické třídění používáme, když potřebujeme naplánovat úlohy z daných závislostí mezi úlohami. V oblasti výpočetní techniky jej většinou používáme pro řešení závislostí symbolů v linkerech, serializaci dat, plánování instrukcí atd. DFS je široce používán v topologickém třídění.

Závěr

V posledních několika cvičeních jsme prozkoumali více o dvou technikách procházení pro grafy, tj. BFS a DFS. Viděli jsme rozdíly i aplikace obou technik. BFS a DFS v zásadě dosahují stejného výsledku při návštěvě všech uzlů grafu, liší se však v pořadí výstupu a způsobu, jakým se to dělá.

Také jsme viděli implementaci obou technik. Zatímco BFS používá frontu, DFS využívá k implementaci techniky zásobníky. Tímto ukončíme tutoriál o technikách procházení grafů. Můžeme také použít BFS a DFS na stromech.

bezplatný stahovač videa z jakékoli stránky plná verze

Dozvíme se více o překlenutí stromů a několika algoritmech k nalezení nejkratší cesty mezi uzly grafu v našem nadcházejícím tutoriálu.

=> Prohlédněte si úplný seznam výukových programů C ++ zde.

Doporučené čtení

^