logo

TechCodeview

Depth First Search eller DFS for en graf

Depth First Traversal (eller DFS) for en graf ligner Dybde Første gennemgang af et træ. Den eneste fangst her er, at i modsætning til træer kan grafer indeholde cyklusser (en knude kan besøges to gange). For at undgå at behandle en node mere end én gang skal du bruge en boolsk besøgt matrix. En graf kan have mere end én DFS-gennemgang.

Eksempel:

Input: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Produktion: DFS fra toppunkt 1: 1 2 0 3
Forklaring:
DFS-diagram:



Eksempel 1

Eksempel 1

Input: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Produktion: DFS fra toppunkt 2: 2 0 1 3
Forklaring:
DFS-diagram:

Eksempel 2

Eksempel 2

Anbefalet praksis DFS of Graph Prøv det!

Hvordan virker DFS?

Dybde-først-søgning er en algoritme til at krydse eller søge i træ- eller grafdatastrukturer. Algoritmen starter ved rodknuden (vælger en vilkårlig knude som rodknude i tilfælde af en graf) og udforsker så langt som muligt langs hver gren, før den går tilbage.

Lad os forstå arbejdet med Dybde første søgning ved hjælp af følgende illustration:

Trin 1: Til at begynde med er stablet og besøgte arrays tomme.

omdøb mappe i linux

Stak og besøgte arrays er tomme i starten.

Trin 2: Besøg 0 og læg dens tilstødende noder, som endnu ikke er besøgt, i stakken.

Besøg node 0 og læg dens tilstødende noder (1, 2, 3) i stakken

Trin 3: Nu, node 1 i toppen af ​​stakken, så besøg node 1 og pop den fra stakken og læg alle dens tilstødende noder, som ikke er besøgt, i stakken.

Besøg node 1

Trin 4: Nu, Node 2 i toppen af ​​stakken, så besøg node 2 og pop den fra stakken og læg alle dens tilstødende noder, som ikke er besøgt (dvs. 3, 4) i stakken.

Besøg node 2 og læg dens ubesøgte tilstødende noder (3, 4) i stakken

Trin 5: Nu, node 4 i toppen af ​​stakken, så besøg node 4 og pop den fra stakken og læg alle dens tilstødende noder, som ikke er besøgt, i stakken.

Besøg node 4

Trin 6: Nu, node 3 i toppen af ​​stakken, så besøg node 3 og pop den fra stakken og læg alle dens tilstødende noder, som ikke er besøgt, i stakken.

Besøg node 3

Nu bliver Stack tom, hvilket betyder, at vi har besøgt alle noderne og vores DFS-gennemløbsender.

Nedenfor er implementeringen af ​​ovenstående tilgang:

C++

type variabler java




// 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øgt;> >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

strengsammenkædning




// 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> 

>

>

Python3




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

>

>

java konverter streng til heltal

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 (); } // Funktion til at tilføje en kant til grafens tomrum AddEdge(int v, int w) { // Tilføj w til v's liste. adj[v].Add(w); } // En funktion brugt af DFS void DFSUtil(int v, bool[] besøgt) { // Marker den aktuelle node som besøgt // og udskriv den besøgt[v] = sand; Console.Write(v + ' '); // Gentages for alle toppunkter // ved siden af ​​denne toppunktliste vList = adj[v]; foreach(var n i vList) { if (!besøgt[n]) DFSUtil(n, besøgt); } } // Funktionen til at udføre DFS-gennemgang. // Den bruger rekursiv DFSUtil() void DFS(int v) { // Marker alle hjørnerne som ikke besøgte // (indstillet som falsk som standard i c#) bool[] visited = new bool[V]; // Kald den rekursive hjælpefunktion // for at udskrive DFS-traversal DFSUtil(v, besøgt); } // 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); Console.WriteLine( 'Følgende er Dybde Første Traversal ' + '(startende fra toppunkt 2)'); // Funktionskald g.DFS(2); Console.ReadKey(); } } // Denne kode er bidraget af techno2mahi> 

>

>

industri og fabrik

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>

Kompleksitetsanalyse af dybde-første søgning:

  • Tidskompleksitet: O(V + E), hvor V er antallet af hjørner og E er antallet af kanter i grafen.
  • Hjælpeplads: O(V + E), da et ekstra besøgt array af størrelse V er påkrævet, og stakstørrelse for iterativt kald til DFS-funktion.