Menu

Dybde første søgning (DFS) C ++ - program til at krydse en graf eller et træ

  • Vigtigste
  • Andet
  • Dybde første søgning (DFS) C ++ - program til at krydse en graf eller et træ

depth first search c program traverse graph

Prøv Vores Instrument Til At Fjerne Problemer

Denne vejledning dækker dybde første søgning (DFS) i C ++, hvor en graf eller et træ er krydset dybt. Du lærer også DFS-algoritme og implementering:

Dybde-første søgning (DFS) er endnu en teknik, der bruges til at krydse et træ eller en graf.

DFS starter med en rodnode eller en startnode og udforsker derefter de tilstødende noder for den aktuelle node ved at gå dybere ind i grafen eller et træ. Dette betyder, at i DFS udforskes noderne dybdegående, indtil der opstår en node uden børn.

Når bladknudepunktet er nået, sporer DFS tilbage og begynder at udforske nogle flere noder på en lignende måde.

=> Hold øje med begyndere C ++ træningsvejledning her.

Dybde-første søgning

Hvad du lærer:

Dybde første søgning (DFS) i C ++

I modsætning til BFS, hvor vi udforsker noderne i bredden, i DFS udforsker vi noderne dybdegående. I DFS bruger vi en stakdatastruktur til lagring af de noder, der udforskes. Kanterne, der fører os til uudforskede noder, kaldes 'opdagelseskanter', mens de kanter, der fører til allerede besøgte noder, kaldes 'blokkanter'.

Dernæst vil vi se algoritmen og pseudokoden til DFS-teknikken.

DFS algoritme

  • Trin 1: Indsæt rodknudepunktet eller startknudepunktet for et træ eller en graf i stakken.
  • Trin 2: Pop det øverste element fra stakken, og føj det til den besøgte liste.
  • Trin 3: Find alle de tilstødende noder på den node, der er markeret som besøgt, og tilføj dem, der endnu ikke er besøgt, til stakken.
  • Trin 4 : Gentag trin 2 og 3, indtil stakken er tom.

Pseudokode

Pseudokoden til DFS er angivet nedenfor.

Pseudokoden til DFS

Fra ovenstående pseudokode bemærker vi, at DFS-algoritmen kaldes rekursivt på hvert toppunkt for at sikre, at alle hjørnerne besøges.

Traversaler med illustrationer

Lad os nu illustrere DFS-gennemgangen af ​​en graf. Af klarhedshensyn vil vi bruge den samme graf, som vi brugte i BFS-illustrationen.

DFS-illustrationer med traversaler

Lad 0 være startknudepunktet eller kildeknudepunktet. Først markerer vi det som besøgt og føjer det til den besøgte liste. Derefter skubber vi alle dens tilstødende noder i stakken.

Skub alle tilstødende noder i stakken

Dernæst tager vi en af ​​de tilstødende noder til behandling, dvs. toppen af ​​stakken, som er 1. Vi markerer den som besøgt ved at tilføje den til den besøgte liste. Se nu efter de tilstødende noder på 1. Da 0 allerede er i den besøgte liste, ignorerer vi den, og vi besøger 2, som er toppen af ​​stakken.

DFS Illustration - Trin 3

Dernæst markerer vi node 2 som besøgt. Dens tilstødende knudepunkt 4 føjes til stakken.

DFS-illustration Trin 4

Dernæst markerer vi 4, som er toppen af ​​stakken som besøgt. Knude 4 har kun knude 2 som sin tilstødende, som allerede er besøgt, derfor ignorerer vi den.

DFS-illustration Trin 5

På dette trin er kun knude 3 til stede i stakken. Dens tilstødende knudepunkt 0 er allerede besøgt, derfor ignorerer vi det. Nu markerer vi 3 som besøgt.

DFS-illustration Trin 6

Nu er stakken tom, og den besøgte liste viser rækkefølgen af ​​dybde-første gennemgang af den givne graf.

Hvis vi observerer den givne graf og traversalsekvensen, bemærker vi, at for DFS-algoritmen krydser vi faktisk grafen dybdegående og sporer den derefter igen for at udforske nye noder.

Implementering af dybde-første søgning

Lad os implementere DFS traversal teknik ved hjælp af 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:'<

Produktion:

Dybde-første gennemgang for den givne graf:

0 1 2 4 3

Vi har igen brugt grafen i programmet, som vi brugte til illustration. Vi ser, at DFS-algoritmen (adskilt i to funktioner) kaldes rekursivt på hvert toppunkt i grafen for at sikre, at alle hjørnerne besøges.

Runtime-analyse

Tidskompleksiteten af ​​DFS er den samme som BFS, dvs. O (| V | + | E |) hvor V er antallet af hjørner og E er antallet af kanter i en given graf.

Svarende til BFS, afhængigt af om grafen er knap befolket eller tæt befolket, vil den dominerende faktor være henholdsvis hjørner eller kanter i beregningen af ​​tidskompleksitet.

Iterativ DFS

Implementeringen vist ovenfor for DFS-teknikken er rekursiv og bruger en funktionskaldestak. Vi har en anden variant til implementering af DFS, dvs. Iterativ dybde-første søgning ”. I dette bruger vi den eksplicitte stak til at holde de besøgte hjørner.

Vi har vist implementeringen af ​​iterativ DFS nedenfor. Bemærk, at implementeringen er den samme som BFS bortset fra den faktor, at vi bruger stack-datastrukturen i stedet for en kø.

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

Produktion:

Output af Iterativ dybde-første gennemgang:

0 3 2 4 1

Vi bruger den samme graf, som vi brugte i vores rekursive implementering. Forskellen i output skyldes, at vi bruger stakken i den iterative implementering. Da stakkene følger LIFO-ordren, får vi en anden sekvens af DFS. For at få den samme rækkefølge vil vi måske indsætte hjørnerne i omvendt rækkefølge.

BFS vs DFS

Indtil videre har vi diskuteret både traversal teknikker til grafer, dvs. BFS og DFS.

Lad os nu se på forskellene mellem de to.

BFSDFS
Står for 'Bredde-første søgning'Står for 'Dybde-første søgning'
Knudepunkterne udforskes bredt efter niveau.Knudepunkterne udforskes dybdegående, indtil der kun er bladknuder og derefter tilbagespores for at udforske andre ubesøgte knudepunkter.
BFS udføres ved hjælp af kødatastruktur.DFS udføres ved hjælp af stack datastruktur.
Langsommere i ydelse.Hurtigere end BFS.
Nyttig til at finde den korteste sti mellem to noder.Bruges hovedsagelig til at registrere cyklusser i grafer.

Anvendelser af DFS

  • Registrering af cyklusser i grafen: Hvis vi finder en bagkant, mens vi udfører DFS i en graf, kan vi konkludere, at grafen har en cyklus. Derfor bruges DFS til at detektere cyklusser i en graf.
  • Stifinding: Givet to hjørner x og y, kan vi finde stien mellem x og y ved hjælp af DFS. Vi starter med toppunkt x og skubber derefter alle hjørnerne på vej til stakken, indtil vi støder på y. Indholdet af stakken giver stien mellem x og y.
  • Minimum spændende træ og korteste sti: DFS-gennemkørsel af den ikke-vægtede graf giver os et minimum, der spænder over træet og den korteste sti mellem noder.
  • Topologisk sortering: Vi bruger topologisk sortering, når vi har brug for at planlægge jobene fra de givne afhængigheder blandt job. Inden for datalogi bruger vi det mest til at løse symbolafhængigheder i linkere, dataserialisering, instruktionsplanlægning osv. DFS bruges i vid udstrækning i topologisk sortering.

Konklusion

I de sidste par tutorials undersøgte vi mere om de to traversale teknikker til grafer, dvs. BFS og DFS. Vi har set forskellene såvel som anvendelserne af begge teknikker. BFS og DFS opnår stort set det samme resultat af at besøge alle noder i en graf, men de adskiller sig i rækkefølgen af ​​output og den måde, det gøres på.

Vi har også set implementeringen af ​​begge teknikker. Mens BFS bruger en kø, bruger DFS stakke til at implementere teknikken. Med dette afslutter vi selvstudiet om traversal teknikker til grafer. Vi kan også bruge BFS og DFS på træer.

bedste mp3 sang downloader til android

Vi lærer mere om spændende træer og et par algoritmer for at finde den korteste vej mellem knudepunkterne i en graf i vores kommende vejledning.

=> Se her for at udforske den komplette C ++ tutorials-liste.

Anbefalet læsning

^