Meny

Dybde første søk (DFS) C ++ - program for å krysse en graf eller et tre

  • Hoved
  • Annen
  • Dybde første søk (DFS) C ++ - program for å krysse en graf eller et tre

depth first search c program traverse graph

Prøv Instrumentet Vårt For Å Eliminere Problemer

Denne opplæringen dekker dybde første søk (DFS) i C ++ der en graf eller et tre er krysset dybden. Du vil også lære DFS algoritme og implementering:

Dybde-første søk (DFS) er enda en teknikk som brukes til å krysse et tre eller en graf.

DFS starter med en rotnode eller en startnode og utforsker deretter de tilstøtende nodene til den nåværende noden ved å gå dypere inn i grafen eller et tre. Dette betyr at nodene i DFS blir utforsket dybdevis til en node uten barn oppstår.

Når bladnoden er nådd, sporer DFS og begynner å utforske flere noder på en lignende måte.

=> Se opp nybegynnere C ++ treningsguide her.

Dybde-første søk

Hva du vil lære:

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

I motsetning til BFS der vi utforsker nodene bredt, i DFS utforsker vi nodene dybdemessig. I DFS bruker vi en stabeldatastruktur for å lagre nodene som utforskes. Kantene som fører oss til uutforskede noder kalles 'discovery-kanter' mens kantene som fører til allerede besøkte noder kalles 'block-kanter'.

Deretter vil vi se algoritmen og pseudokoden for DFS-teknikken.

DFS algoritme

  • Trinn 1: Sett rotnoden eller startnoden til et tre eller en graf i stabelen.
  • Steg 2: Popp det øverste elementet fra bunken og legg det til den besøkte listen.
  • Trinn 3: Finn alle tilstøtende noder til noden som er merket besøkt, og legg til de som ennå ikke er besøkt, i bunken.
  • Trinn 4 : Gjenta trinn 2 og 3 til bunken er tom.

Pseudokode

Pseudokoden for DFS er gitt nedenfor.

Pseudokoden for DFS

Fra ovennevnte pseudokode merker vi at DFS-algoritmen kalles rekursivt på hvert toppunkt for å sikre at alle toppunktene blir besøkt.

Gjennomganger med illustrasjoner

La oss nå illustrere DFS-traversering av en graf. For klarhets skyld vil vi bruke den samme grafen som vi brukte i BFS-illustrasjonen.

DFS Illustrasjoner med traversaler

La 0 være startnoden eller kildenoden. Først markerer vi den som besøkt og legger den til den besøkte listen. Så skyver vi alle tilstøtende noder i bunken.

Skyv alle tilstøtende noder i bunken

Deretter tar vi en av de tilstøtende nodene for å behandle, dvs. toppen av stabelen som er 1. Vi markerer den som besøkt ved å legge den til den besøkte listen. Se etter de tilstøtende nodene til 1. Ettersom 0 allerede er i den besøkte listen, ignorerer vi den og vi besøker 2 som er toppen av bunken.

DFS Illustrasjon - Trinn 3

Deretter merker vi node 2 som besøkt. Den tilstøtende noden 4 er lagt til stabelen.

DFS Illustrasjon Trinn 4

Deretter markerer vi 4 som er toppen av bunken som besøkt. Node 4 har bare node 2 som den tilstøtende som allerede er besøkt, derfor ignorerer vi den.

DFS Illustrasjon Trinn 5

På dette stadiet er bare node 3 til stede i stabelen. Den tilstøtende noden 0 er allerede besøkt, derfor ignorerer vi den. Nå merker vi 3 som besøkt.

DFS Illustrasjon Trinn 6

Nå er stakken tom og den besøkte listen viser sekvensen til dybde-første traversering av den gitte grafen.

Hvis vi observerer den gitte grafen og traversalsekvensen, legger vi merke til at for DFS-algoritmen, krysser vi virkelig grafen dybdemessig og sporer den deretter igjen for å utforske nye noder.

Implementering av dybde-første søk

La oss implementere DFS traversal-teknikken ved hjelp av 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:'<

Produksjon:

Dybde-første traversering for den gitte grafen:

0 1 2 4 3

Vi har igjen brukt grafen i programmet som vi brukte til illustrasjonsformål. Vi ser at DFS-algoritmen (delt inn i to funksjoner) kalles rekursivt på hvert toppunkt i grafen for å sikre at alle toppunktene blir besøkt.

Runtime-analyse

Tidskompleksiteten til DFS er den samme som BFS, dvs. O (| V | + | E |) hvor V er antall hjørner og E er antall kanter i en gitt graf.

I likhet med BFS, avhengig av om grafen er knapt befolket eller tett befolket, vil den dominerende faktoren være henholdsvis hjørner eller kanter i beregningen av tidskompleksitet.

Iterativ DFS

Implementeringen vist ovenfor for DFS-teknikken er rekursiv og bruker en funksjonskallestabel. Vi har en annen variant for implementering av DFS, dvs. Iterativ dybde-første søk ”. I dette bruker vi den eksplisitte stakken for å holde de besøkte toppunktene.

Vi har vist implementeringen for iterativ DFS nedenfor. Merk at implementeringen er den samme som BFS bortsett fra faktoren at vi bruker stabeldatastrukturen 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; }

Produksjon:

Resultat av Iterativ dybde-første gjennomgang:

0 3 2 4 1

Vi bruker den samme grafen som vi brukte i vår rekursive implementering. Forskjellen i utgang er fordi vi bruker stakken i iterativ implementering. Ettersom stablene følger LIFO-ordren, får vi en annen sekvens av DFS. For å få samme sekvens, kan det være lurt å sette inn hjørnene i omvendt rekkefølge.

BFS vs DFS

Så langt har vi diskutert både traversal teknikker for grafer, dvs. BFS og DFS.

La oss nå se på forskjellene mellom de to.

BFSDFS
Står for “Bredde-første søk”Står for “Dybde-første søk”
Knutepunktene utforskes bredt nivå etter nivå.Nodene blir utforsket dybdemessig til det bare er bladnoder og deretter spores tilbake for å utforske andre ubesøkte noder.
BFS utføres ved hjelp av kødatastruktur.DFS utføres ved hjelp av stabeldatastrukturen.
Tregere i ytelse.Raskere enn BFS.
Nyttig for å finne den korteste stien mellom to noder.Brukes mest for å oppdage sykluser i grafer.

Anvendelser av DFS

  • Oppdage sykluser i grafen: Hvis vi finner en bakkant mens vi utfører DFS i en graf, kan vi konkludere med at grafen har en syklus. Derfor brukes DFS til å oppdage syklusene i en graf.
  • Stifinning: Gitt to hjørner x og y, kan vi finne stien mellom x og y ved hjelp av DFS. Vi starter med toppunkt x og skyver deretter alle toppunktene på vei til stabelen til vi møter y. Innholdet i stabelen gir banen mellom x og y.
  • Minimum spennende tre og korteste vei: DFS-traversering av den uvektede grafen gir oss et minimum av tre og kortest vei mellom noder.
  • Topologisk sortering: Vi bruker topologisk sortering når vi trenger å planlegge jobbene fra de gitte avhengighetene blant jobbene. I informatikkfeltet bruker vi det mest for å løse symbolavhengigheter i lenker, dataserialisering, instruksjonsplanlegging, etc. DFS er mye brukt i topologisk sortering.

Konklusjon

I de siste par opplæringene utforsket vi mer om de to traversale teknikkene for grafer, dvs. BFS og DFS. Vi har sett forskjellene så vel som anvendelsene av begge teknikkene. BFS og DFS oppnår i utgangspunktet det samme utfallet av å besøke alle noder i en graf, men de varierer i rekkefølgen på utdataene og måten det gjøres på.

Vi har også sett implementeringen av begge teknikkene. Mens BFS bruker en kø, bruker DFS stabler for å implementere teknikken. Med dette avslutter vi opplæringen om traversale teknikker for grafer. Vi kan også bruke BFS og DFS på trær.

sett inn node i binært tre java

Vi vil lære mer om å sprenge trær og et par algoritmer for å finne den korteste veien mellom nodene i en graf i vår kommende opplæring.

=> Se her for å utforske hele C ++ opplæringslisten.

Anbefalt lesing

^