Meniu

Programul C ++ pentru căutarea în adâncime (DFS) pentru a traversa un grafic sau un arbore

  • Principal
  • Alte
  • Programul C ++ pentru căutarea în adâncime (DFS) pentru a traversa un grafic sau un arbore

depth first search c program traverse graph

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

Acest tutorial acoperă prima căutare a adâncimii (DFS) în C ++ în care un grafic sau un arbore este parcurs în adâncime. Veți învăța, de asemenea, algoritmul și implementarea DFS:

Căutarea în profunzime (DFS) este încă o altă tehnică utilizată pentru a traversa un copac sau un grafic.

DFS începe cu un nod rădăcină sau cu un nod de pornire și apoi explorează nodurile adiacente ale nodului curent mergând mai adânc în grafic sau într-un arbore. Aceasta înseamnă că în DFS nodurile sunt explorate în profunzime până când se întâlnește un nod fără copii.

Odată ce nodul frunză este atins, DFS retrogradează și începe să exploreze câteva noduri în mod similar.

=> Fii atent la Ghidul de instruire pentru începători C ++ aici.

Căutare în profunzime

Ce veți învăța:

Căutare în profunzime (DFS) în C ++

Spre deosebire de BFS în care explorăm nodurile în sens larg, în DFS explorăm nodurile în profunzime. În DFS folosim o structură de date stivă pentru stocarea nodurilor explorate. Marginile care ne conduc spre noduri neexplorate se numesc „margini de descoperire”, în timp ce marginile care duc la noduri deja vizitate se numesc „margini de bloc”.

Apoi, vom vedea algoritmul și pseudo-codul pentru tehnica DFS.

Algoritm DFS

  • Pasul 1: Introduceți nodul rădăcină sau nodul de pornire al unui copac sau un grafic în stivă.
  • Pasul 2: Scoateți elementul de sus din stivă și adăugați-l la lista vizitată.
  • Pasul 3: Găsiți toate nodurile adiacente ale nodului marcat ca vizitat și adăugați-le pe cele care nu sunt încă vizitate.
  • Pasul 4 : Repetați pașii 2 și 3 până când stiva este goală.

Pseudo cod

Pseudo-codul pentru DFS este dat mai jos.

Pseudo-codul pentru DFS

Din pseudo-codul de mai sus, observăm că algoritmul DFS este apelat recursiv pe fiecare vârf pentru a se asigura că toate vârfurile sunt vizitate.

Traversări cu ilustrații

Să ilustrăm acum traversarea DFS a unui grafic. Pentru claritate, vom folosi același grafic pe care l-am folosit în ilustrația BFS.

Ilustrații DFS cu traversări

Fie 0 nodul de pornire sau nodul sursă. În primul rând, îl marcăm ca vizitat și îl adăugăm la lista vizitată. Apoi împingem toate nodurile sale adiacente în stivă.

Împingeți toate nodurile adiacente din stivă

Apoi, luăm unul dintre nodurile adiacente pentru a procesa, adică partea de sus a stivei, care este 1. Îl marcăm ca vizitat adăugându-l în lista vizitată. Acum căutați nodurile adiacente 1. Deoarece 0 este deja în lista vizitată, îl ignorăm și vizităm 2, care este partea de sus a stivei.

Ilustrație DFS - Pasul 3

Apoi, marcăm nodul 2 ca vizitat. Nodul său adiacent 4 este adăugat la stivă.

Ilustrația DFS Pasul 4

Apoi, marchăm 4 care este partea de sus a stivei așa cum a fost vizitată. Nodul 4 are adiacent doar nodul 2, care este deja vizitat, de aceea îl ignorăm.

Ilustrația DFS Pasul 5

În această etapă, doar nodul 3 este prezent în stivă. Nodul său adiacent 0 este deja vizitat, de aceea îl ignorăm. Acum marchăm 3 ca vizitate.

Ilustrația DFS Pasul 6

Acum stiva este goală și lista vizitată arată secvența parcurgerii în adâncime a graficului dat.

Dacă observăm graficul dat și secvența de traversare, observăm că, pentru algoritmul DFS, traversăm într-adevăr graficul în profunzime și apoi îl retrogradăm pentru a explora noi noduri.

Implementarea căutării în profunzime

Să implementăm tehnica de traversare DFS folosind 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:'<

Ieșire:

Prima traversare a adâncimii pentru graficul dat:

0 1 2 4 3

Am folosit din nou graficul din program pe care l-am folosit în scop ilustrativ. Vedem că algoritmul DFS (separat în două funcții) este apelat recursiv pe fiecare vârf din grafic pentru a se asigura că toate vârfurile sunt vizitate.

Analiza Runtime

Complexitatea în timp a DFS este aceeași cu BFS, adică O (| V | + | E |) unde V este numărul de vârfuri și E este numărul de muchii dintr-un grafic dat.

Similar cu BFS, în funcție de faptul dacă graficul este puțin populat sau dens populat, factorul dominant va fi vârfurile sau respectiv muchiile în calculul complexității timpului.

DFS iterativ

Implementarea prezentată mai sus pentru tehnica DFS are caracter recursiv și folosește o stivă de apeluri funcționale. Avem o altă variantă pentru implementarea DFS, adică „ Căutare profundă iterativă-prima ”. În aceasta, folosim stiva explicită pentru a menține vârfurile vizitate.

Am arătat mai jos implementarea pentru DFS iterativ. Rețineți că implementarea este aceeași cu BFS, cu excepția factorului în care folosim structura de date a stivei în loc de o coadă.

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

Ieșire:

Ieșirea adâncimii iterative - prima traversare:

0 3 2 4 1

Folosim același grafic pe care l-am folosit în implementarea recursivă. Diferența de ieșire se datorează faptului că folosim stiva în implementarea iterativă. Pe măsură ce stivele respectă ordinea LIFO, obținem o secvență diferită de DFS. Pentru a obține aceeași secvență, am putea dori să inserăm vârfurile în ordine inversă.

BFS vs DFS

Până acum am discutat atât tehnicile de traversare pentru grafice, adică BFS și DFS.

Acum să analizăm diferențele dintre cele două.

BFSDFS
Stabilește pentru „Căutare pe lățime”Stabilește „Căutare în profunzime”
Nodurile sunt explorate în funcție de lățime nivel cu nivel.Nodurile sunt explorate în profunzime până când există doar noduri frunze și apoi sunt retrocedate pentru a explora alte noduri nevizitate.
BFS se realizează cu ajutorul structurii de date a cozii.DFS se realizează cu ajutorul structurii de date a stivei.
Performanță mai lentă.Mai rapid decât BFS.
Util pentru găsirea celei mai scurte căi între două noduri.Folosit mai ales pentru a detecta cicluri în grafice.

Aplicații ale DFS

  • Detectarea ciclurilor în grafic: Dacă găsim o margine din spate în timp ce efectuăm DFS într-un grafic, putem concluziona că graficul are un ciclu. Prin urmare, DFS este utilizat pentru a detecta ciclurile într-un grafic.
  • Găsirea drumului: Având în vedere două vârfuri x și y, putem găsi calea dintre x și y folosind DFS. Începem cu vârful x și apoi împingem toate vârfurile pe drumul către stivă până când îl întâlnim pe y. Conținutul stivei oferă calea dintre x și y.
  • Arborele minim care se întinde și cea mai scurtă cale: Traversarea DFS a graficului ne-ponderat ne oferă un arbore de întindere minim și cea mai scurtă cale între noduri.
  • Sortare topologică: Folosim sortare topologică atunci când trebuie să planificăm joburile din dependențele date dintre joburi. În domeniul informaticii, îl folosim mai ales pentru rezolvarea dependențelor de simboluri în linkere, serializarea datelor, planificarea instrucțiunilor etc. DFS este utilizat pe scară largă în sortarea topologică.

Concluzie

În ultimele două tutoriale, am explorat mai multe despre cele două tehnici de traversare pentru grafice, adică BFS și DFS. Am văzut diferențele, precum și aplicațiile ambelor tehnici. BFS și DFS obțin practic același rezultat al vizitării tuturor nodurilor unui grafic, dar diferă în ordinea ieșirii și în modul în care este realizat.

De asemenea, am văzut implementarea ambelor tehnici. În timp ce BFS folosește o coadă, DFS folosește stive pentru a implementa tehnica. Cu aceasta, încheiem tutorialul cu privire la tehnicile de traversare pentru grafice. Putem folosi și BFS și DFS pe copaci.

întrebări și răspunsuri de programare Java pentru test scris

Vom afla mai multe despre întinderea copacilor și câțiva algoritmi pentru a găsi cea mai scurtă cale între nodurile unui grafic în următorul nostru tutorial.

=> Consultați aici pentru a explora lista completă de tutoriale C ++.

Lectură recomandată

^