Depth First Traversal (eller DFS) för en graf liknar Djup Första genomgång av ett träd. Den enda haken här är att, till skillnad från träd, kan grafer innehålla cykler (en nod kan besökas två gånger). För att undvika att bearbeta en nod mer än en gång, använd en boolesk besökt array. En graf kan ha mer än en DFS-traversering.
Exempel:
Rekommenderad övning DFS of Graph Prova det!Inmatning: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Produktion: DFS från vertex 1 : 1 2 0 3
Förklaring:
DFS-diagram:
Exempel 1
Inmatning: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Produktion: DFS från vertex 2: 2 0 1 3
Förklaring:
DFS-diagram:Exempel 2
Hur fungerar DFS?
Djup-först-sökning är en algoritm för att korsa eller söka träd- eller grafdatastrukturer. Algoritmen börjar vid rotnoden (väljar någon godtycklig nod som rotnod i fallet med en graf) och utforskar så långt som möjligt längs varje gren innan den backas.
Låt oss förstå hur det fungerar Djup första sökning med hjälp av följande illustration:
Steg 1: Initialt stack och besökta arrayer är tomma.
java sträng indexofStack och besökta arrayer är tomma initialt.
Steg 2: Besök 0 och placera dess närliggande noder som inte har besökts ännu i stacken.
Besök nod 0 och placera dess intilliggande noder (1, 2, 3) i stacken
Steg 3: Nu, nod 1 högst upp i stacken, så besök nod 1 och släpp den från stacken och lägg alla dess närliggande noder som inte besöks i stacken.
Besök nod 1
Steg 4: Nu, Nod 2 högst upp i stacken, så besök nod 2 och släpp den från stacken och lägg alla dess närliggande noder som inte besöks (dvs. 3, 4) i stacken.
Besök nod 2 och placera dess obesökta intilliggande noder (3, 4) i stacken
Steg 5: Nu, nod 4 högst upp i stacken, så besök nod 4 och släpp den från stacken och lägg alla dess närliggande noder som inte besöks i stacken.
Besök nod 4
Steg 6: Nu, nod 3 högst upp i stacken, så besök nod 3 och släpp den från stacken och lägg alla dess närliggande noder som inte besöks i stacken.
j e s tBesök nod 3
Nu blir Stack tom, vilket betyder att vi har besökt alla noder och vår DFS-traversal slutar.
Nedan är implementeringen av ovanstående tillvägagångssätt:
C++
// C++ program to print DFS traversal from> // a given vertex in a given graph> #include> using> namespace> std;> // Graph class represents a directed graph> // using adjacency list representation> class> Graph {> public>:> >map<>int>,>bool>>besökt;> >map<>int>, list<>int>>> adj;> >// Function to add an edge to graph> >void> addEdge(>int> v,>int> w);> >// DFS traversal of the vertices> >// reachable from v> >void> DFS(>int> v);> };> void> Graph::addEdge(>int> v,>int> w)> {> >// Add w to v’s list.> >adj[v].push_back(w);> }> void> Graph::DFS(>int> v)> {> >// Mark the current node as visited and> >// print it> >visited[v] =>true>;> >cout << v <<>' '>;> >// Recur for all the vertices adjacent> >// to this vertex> >list<>int>>::iterator i;> >for> (i = adj[v].begin(); i != adj[v].end(); ++i)> >if> (!visited[*i])> >DFS(*i);> }> // Driver code> int> main()> {> >// Create a graph given in the above diagram> >Graph g;> >g.addEdge(0, 1);> >g.addEdge(0, 2);> >g.addEdge(1, 2);> >g.addEdge(2, 0);> >g.addEdge(2, 3);> >g.addEdge(3, 3);> >cout <<>'Following is Depth First Traversal'> >' (starting from vertex 2)
'>;> >// Function call> >g.DFS(2);> >return> 0;> }> // improved by Vishnudev C> |
>
>
Java
// Java program to print DFS traversal> // from a given graph> import> java.io.*;> import> java.util.*;> // This class represents a> // directed graph using adjacency> // list representation> class> Graph {> >private> int> V;> >// Array of lists for> >// Adjacency List Representation> >private> LinkedList adj[];> >// Constructor> >@SuppressWarnings>(>'unchecked'>) Graph(>int> v)> >{> >V = v;> >adj =>new> LinkedList[v];> >for> (>int> i =>0>; i adj[i] = new LinkedList(); } // Function to add an edge into the graph void addEdge(int v, int w) { // Add w to v's list. adj[v].add(w); } // A function used by DFS void DFSUtil(int v, boolean visited[]) { // Mark the current node as visited and print it visited[v] = true; System.out.print(v + ' '); // Recur for all the vertices adjacent to this // vertex Iterator i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil(n, visited); } } // The function to do DFS traversal. // It uses recursive DFSUtil() void DFS(int v) { // Mark all the vertices as // not visited(set as // false by default in java) boolean visited[] = new boolean[V]; // Call the recursive helper // function to print DFS // traversal DFSUtil(v, visited); } // Driver Code public static void main(String args[]) { Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); System.out.println( 'Following is Depth First Traversal ' + '(starting from vertex 2)'); // Function call g.DFS(2); } } // This code is contributed by Aakash Hasija> |
>
string.format i java
>
Python3
semantiskt fel
# Python3 program to print DFS traversal> # from a given graph> from> collections>import> defaultdict> # This class represents a directed graph using> # adjacency list representation> class> Graph:> ># Constructor> >def> __init__(>self>):> ># Default dictionary to store graph> >self>.graph>=> defaultdict(>list>)> > ># Function to add an edge to graph> >def> addEdge(>self>, u, v):> >self>.graph[u].append(v)> > ># A function used by DFS> >def> DFSUtil(>self>, v, visited):> ># Mark the current node as visited> ># and print it> >visited.add(v)> >print>(v, end>=>' '>)> ># Recur for all the vertices> ># adjacent to this vertex> >for> neighbour>in> self>.graph[v]:> >if> neighbour>not> in> visited:> >self>.DFSUtil(neighbour, visited)> > ># The function to do DFS traversal. It uses> ># recursive DFSUtil()> >def> DFS(>self>, v):> ># Create a set to store visited vertices> >visited>=> set>()> ># Call the recursive helper function> ># to print DFS traversal> >self>.DFSUtil(v, visited)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph()> >g.addEdge(>0>,>1>)> >g.addEdge(>0>,>2>)> >g.addEdge(>1>,>2>)> >g.addEdge(>2>,>0>)> >g.addEdge(>2>,>3>)> >g.addEdge(>3>,>3>)> >print>(>'Following is Depth First Traversal (starting from vertex 2)'>)> > ># Function call> >g.DFS(>2>)> # This code is contributed by Neelam Yadav> |
>
>
C#
// C# program to print DFS traversal> // from a given graph> using> System;> using> System.Collections.Generic;> // This class represents a directed graph> // using adjacency list representation> class> Graph {> >private> int> V;> >// Array of lists for> >// Adjacency List Representation> >private> List<>int>>[] adj;> >// Constructor> >Graph(>int> v)> >{> >V = v;> >adj =>new> List<>int>>[i ];> >for> (>int> i = 0; i adj[i] = new List |
>
>
motstridig sökning
Javascript
// Javascript program to print DFS> // traversal from a given> // graph> // This class represents a> // directed graph using adjacency> // list representation> class Graph> {> > >// Constructor> >constructor(v)> >{> >this>.V = v;> >this>.adj =>new> Array(v);> >for>(let i = 0; i this.adj[i] = []; } // Function to add an edge into the graph addEdge(v, w) { // Add w to v's list. this.adj[v].push(w); } // A function used by DFS DFSUtil(v, visited) { // Mark the current node as visited and print it visited[v] = true; console.log(v + ' '); // Recur for all the vertices adjacent to this // vertex for(let i of this.adj[v].values()) { let n = i if (!visited[n]) this.DFSUtil(n, visited); } } // The function to do DFS traversal. // It uses recursive // DFSUtil() DFS(v) { // Mark all the vertices as // not visited(set as // false by default in java) let visited = new Array(this.V); for(let i = 0; i |
>
>Produktion
Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>
Komplexitetsanalys av djup första sökning:
- Tidskomplexitet: O(V + E), där V är antalet hörn och E är antalet kanter i grafen.
- Hjälputrymme: O(V + E), eftersom en extra besökt array av storlek V krävs, och stackstorlek för iterativt anrop till DFS-funktionen.