logo

TechCodeview

Tiefensuche oder DFS für ein Diagramm

Tiefendurchquerung (oder DFS) für einen Graphen ist ähnlich Tiefendurchquerung eines Baumes. Der einzige Haken hier ist, dass Diagramme im Gegensatz zu Bäumen Zyklen enthalten können (ein Knoten kann zweimal besucht werden). Um zu vermeiden, dass ein Knoten mehr als einmal verarbeitet wird, verwenden Sie ein boolesches besuchtes Array. Ein Diagramm kann mehr als einen DFS-Durchlauf haben.

Beispiel:

Eingang: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Ausgabe: DFS vom Scheitelpunkt 1 : 1 2 0 3
Erläuterung:
DFS-Diagramm:



Beispiel 1

Beispiel 1

Eingang: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Ausgabe: DFS von Scheitelpunkt 2: 2 0 1 3
Erläuterung:
DFS-Diagramm:

Beispiel 2

Beispiel 2

Empfohlene Praxis DFS of Graph Probieren Sie es aus!

Wie funktioniert DFS?

Die Tiefensuche ist ein Algorithmus zum Durchsuchen oder Durchsuchen von Baum- oder Diagrammdatenstrukturen. Der Algorithmus beginnt am Wurzelknoten (wobei er im Fall eines Diagramms einen beliebigen Knoten als Wurzelknoten auswählt) und erkundet so weit wie möglich jeden Zweig entlang, bevor er zurückverfolgt.

Lassen Sie uns die Funktionsweise von verstehen Tiefensuche mit Hilfe der folgenden Abbildung:

Schritt 1: Stapel- und besuchte Arrays sind zunächst leer.

Zentrieren eines Bildes in CSS

Stapel- und besuchte Arrays sind zunächst leer.

Schritt 2: Besuchen Sie 0 und legen Sie die angrenzenden Knoten, die noch nicht besucht wurden, in den Stapel.

Besuchen Sie Knoten 0 und legen Sie die angrenzenden Knoten (1, 2, 3) in den Stapel

Schritt 3: Jetzt befindet sich Knoten 1 oben auf dem Stapel. Besuchen Sie also Knoten 1, nehmen Sie ihn vom Stapel und legen Sie alle benachbarten Knoten, die nicht besucht werden, in den Stapel.

Besuchen Sie Knoten 1

Schritt 4: Jetzt, Knoten 2 befindet sich ganz oben auf dem Stapel. Besuchen Sie also Knoten 2, nehmen Sie ihn vom Stapel und legen Sie alle benachbarten Knoten, die nicht besucht werden (d. h. 3, 4), in den Stapel.

Maschinelles Lernen und Typen

Besuchen Sie Knoten 2 und legen Sie seine nicht besuchten Nachbarknoten (3, 4) in den Stapel

Schritt 5: Jetzt befindet sich Knoten 4 oben auf dem Stapel. Besuchen Sie also Knoten 4, nehmen Sie ihn vom Stapel und legen Sie alle benachbarten Knoten, die nicht besucht werden, in den Stapel.

Besuchen Sie Knoten 4

Schritt 6: Jetzt befindet sich Knoten 3 oben auf dem Stapel. Besuchen Sie also Knoten 3, nehmen Sie ihn vom Stapel und legen Sie alle benachbarten Knoten, die nicht besucht werden, in den Stapel.

Besuchen Sie Knoten 3

Jetzt ist der Stapel leer, was bedeutet, dass wir alle Knoten besucht haben und unsere DFS-Durchquerung endet.

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

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>>besucht;> >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> 

>

>

Array Java hinzufügen

Python3




Versuchen Sie es mit Catch Catch Java
# 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>>[ in ];> >for> (>int> i = 0; i adj[i] = new List (); } // Funktion zum Hinzufügen einer Kante zum Diagramm void AddEdge(int v, int w) { // w zur Liste von v hinzufügen. adj[v].Add(w); } // Eine von DFS verwendete Funktion void DFSUtil(int v, bool[] besuchte) { // Markiere den aktuellen Knoten als besucht // und drucke ihn aus besuchte[v] = true; Console.Write(v + ' '); // Wiederholung für alle Scheitelpunkte // neben dieser Scheitelpunktliste vList = adj[v]; foreach(var n in vList) { if (!visited[n]) DFSUtil(n, besuchte); } } // Die Funktion zur DFS-Durchquerung. // Es verwendet rekursives DFSUtil() void DFS(int v) { // Alle Scheitelpunkte als nicht besucht markieren // (in c# standardmäßig auf „false“ gesetzt) ​​bool[] besuchte = new bool[V]; // Rufen Sie die rekursive Hilfsfunktion // auf, um die DFS-Durchquerung zu drucken DFSUtil(v, besuchte); } // Treibercode 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( 'Es folgt die Tiefendurchquerung ' + '(beginnend mit Scheitelpunkt 2)'); // Funktionsaufruf g.DFS(2); Console.ReadKey(); } } // Dieser Code wurde von techno2mahi>'> beigesteuert 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  // 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  
  
 
    
 
>
 
    
 
>
 
  Ausgabe  
 
Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>
 
 Komplexitätsanalyse der Tiefensuche: 
 
     
  •     Zeitkomplexität:    O(V + E), wobei V die Anzahl der Eckpunkte und E die Anzahl der Kanten im Diagramm ist.
    •  
  •     Hilfsraum:    O(V + E), da ein zusätzlich besuchtes Array der Größe V und eine Stapelgröße für den iterativen Aufruf der DFS-Funktion erforderlich sind.
    •