Meny

Djup första sökning (DFS) C ++ - program för att korsa en graf eller ett träd

  • Huvud
  • Övrig
  • Djup första sökning (DFS) C ++ - program för att korsa en graf eller ett träd

depth first search c program traverse graph

Prova Vårt Instrument För Att Eliminera Problem

Denna handledning täcker djup första sökning (DFS) i C ++ där en graf eller ett träd passeras djupt. Du lär dig också DFS-algoritm och implementering:

Djup-första sökning (DFS) är ännu en teknik som används för att korsa ett träd eller en graf.

DFS börjar med en rotnod eller en startnod och utforskar sedan de intilliggande noderna för den aktuella noden genom att gå djupare in i diagrammet eller ett träd. Detta innebär att i DFS undersöks noderna djupt tills en nod utan barn påträffas.

När bladnoden nås, spårar DFS tillbaka och börjar utforska några fler noder på ett liknande sätt.

=> Se upp för nybörjare C ++ träningsguide här.

Djup-första sökning

Vad du kommer att lära dig:

Depth First Search (DFS) In C ++

Till skillnad från BFS där vi utforskar noderna på bredden, i DFS utforskar vi noderna djupgående. I DFS använder vi en stapeldatastruktur för att lagra de noder som utforskas. Kanterna som leder oss till outforskade noder kallas 'upptäckkanter' medan kanterna som leder till redan besökta noder kallas 'blockkanter'.

Därefter ser vi algoritmen och pseudokoden för DFS-tekniken.

DFS-algoritm

  • Steg 1: Sätt in rotnoden eller startnoden för ett träd eller ett diagram i stacken.
  • Steg 2: Poppa översta objektet från stacken och lägg till det i den besökta listan.
  • Steg 3: Hitta alla intilliggande noder för noden som är markerad som besökt och lägg till de som ännu inte har besökt, i stacken.
  • Steg 4 : Upprepa steg 2 och 3 tills stacken är tom.

Pseudokod

Pseudokoden för DFS ges nedan.

Pseudokoden för DFS

Från ovanstående pseudokod märker vi att DFS-algoritmen anropas rekursivt på varje toppunkt för att säkerställa att alla topparna besöks.

Traversaler med illustrationer

Låt oss nu illustrera DFS-genomgången av en graf. För tydlighetsändamål kommer vi att använda samma graf som vi använde i BFS-illustrationen.

DFS-illustrationer med traversaler

Låt 0 vara startnoden eller källnoden. Först markerar vi det som besökt och lägger till det i den besökta listan. Sedan skjuter vi alla dess intilliggande noder i stacken.

Skjut in alla intilliggande noder i stacken

Därefter tar vi en av de intilliggande noderna för att bearbeta, dvs. toppen av stapeln som är 1. Vi markerar den som besökt genom att lägga till den i den besökta listan. Leta nu efter intilliggande noder 1. Eftersom 0 redan finns i den besökta listan ignorerar vi den och vi besöker 2 som är toppen av stacken.

DFS Illustration - Steg 3

Därefter markerar vi nod 2 som besökt. Dess intilliggande nod 4 läggs till stapeln.

DFS-illustration Steg 4

Därefter markerar vi 4 som är toppen av stacken som besökt. Nod 4 har endast nod 2 som dess angränsande som redan har besökts, därför ignorerar vi den.

DFS-illustration Steg 5

I detta skede finns endast nod 3 i stacken. Dess intilliggande nod 0 är redan besökt, därför ignorerar vi den. Nu markerar vi 3 som besökt.

DFS-illustration Steg 6

Nu är stacken tom och den besökta listan visar sekvensen för djup-första genomgången av den angivna grafen.

Om vi ​​följer den angivna grafen och traverssekvensen märker vi att för DFS-algoritmen korsar vi verkligen diagrammet djupgående och sedan backar det igen för att utforska nya noder.

Depth-First Search Implementation

Låt oss implementera DFS traversal-teknik med 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:

Djup-första genomgång för den angivna grafen:

0 1 2 4 3

Vi har återigen använt diagrammet i programmet som vi använde för illustrationsändamål. Vi ser att DFS-algoritmen (uppdelad i två funktioner) anropas rekursivt på varje toppunkt i diagrammet för att säkerställa att alla topparna besöks.

Runtime-analys

Tidskomplexiteten för DFS är densamma som BFS, dvs. O (| V | + | E |) där V är antalet hörnpunkter och E är antalet kanter i en given graf.

I likhet med BFS, beroende på om grafen är knappt befolkad eller tätbefolkad, kommer den dominerande faktorn att vara hörn respektive kanter vid beräkning av tidskomplexitet.

Iterativ DFS

Implementeringen som visas ovan för DFS-tekniken är rekursiv till sin natur och den använder en funktionssamtalstack. Vi har en annan variant för att implementera DFS, dvs. Iterativ djup-första sökning ”. I detta använder vi den explicita stacken för att hålla de besökta hörnpunkterna.

Vi har visat implementeringen för iterativ DFS nedan. Observera att implementeringen är densamma som BFS förutom den faktor som vi använder stapeldatastrukturen istället för 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 of Iterative Depth-first traversal:

0 3 2 4 1

Vi använder samma diagram som vi använde i vårt rekursiva genomförande. Skillnaden i output beror på att vi använder stacken i iterativ implementering. När staplarna följer LIFO-ordningen får vi en annan sekvens av DFS. För att få samma sekvens kanske vi vill infoga topparna i omvänd ordning.

BFS vs DFS

Hittills har vi diskuterat både traversaltekniker för grafer, dvs. BFS och DFS.

Låt oss nu titta på skillnaderna mellan de två.

BFSDFS
Står för 'Bredd-första sökning'Står för 'Djup-första sökning'
Noderna utforskas breddvis nivå för nivå.Noderna utforskas djupvis tills det bara finns bladnoder och sedan spåras för att utforska andra obesökta noder.
BFS utförs med hjälp av ködatastruktur.DFS utförs med hjälp av stapeldatastrukturen.
Långsammare i prestanda.Snabbare än BFS.
Användbar för att hitta den kortaste vägen mellan två noder.Används mest för att upptäcka cykler i grafer.

Tillämpningar av DFS

  • Upptäcka cykler i diagrammet: Om vi ​​hittar en bakkant när vi utför DFS i en graf kan vi dra slutsatsen att grafen har en cykel. Därför används DFS för att upptäcka cyklerna i ett diagram.
  • Pathfinding: Med tanke på två hörn x och y kan vi hitta vägen mellan x och y med DFS. Vi börjar med vertex x och trycker sedan på alla hörn på vägen till stacken tills vi stöter på y. Innehållet i stacken ger sökvägen mellan x och y.
  • Minsta spännande träd och kortaste väg: DFS-genomkörning av det oviktade diagrammet ger oss ett minimalt spännande träd och kortaste väg mellan noder.
  • Topologisk sortering: Vi använder topologisk sortering när vi behöver schemalägga jobben från de angivna beroenden bland jobb. Inom datavetenskapsområdet använder vi det mest för att lösa symbolberoenden i länkar, dataserialisering, instruktionsplanering etc. DFS används ofta i topologisk sortering.

Slutsats

Under de senaste para tutorials utforskade vi mer om de två traversalteknikerna för grafer, dvs. BFS och DFS. Vi har sett skillnaderna såväl som tillämpningarna av båda teknikerna. BFS och DFS uppnår i princip samma resultat när man besöker alla noder i ett diagram, men de skiljer sig åt i ordningen för utdata och hur det görs.

Vi har också sett implementeringen av båda teknikerna. Medan BFS använder en kö använder DFS stackar för att implementera tekniken. Med detta avslutar vi handledningen om traversal tekniker för grafer. Vi kan också använda BFS och DFS på träd.

gratis youtube till mp4-omvandlare för mac

Vi kommer att lära oss mer om spännande träd och ett par algoritmer för att hitta den kortaste vägen mellan noderna i en graf i vår kommande handledning.

=> Se här för att utforska listan med fullständiga C ++ -studier.

Rekommenderad läsning

^