logo

TechCodeview

Cerca en profunditat o DFS per a un gràfic

Primer recorregut de profunditat (o DFS) perquè un gràfic és semblant a Profunditat Primera travessa d'un arbre. L'únic problema aquí és que, a diferència dels arbres, els gràfics poden contenir cicles (un node es pot visitar dues vegades). Per evitar processar un node més d'una vegada, utilitzeu una matriu booleana visitada. Un gràfic pot tenir més d'un recorregut DFS.

Exemple:

Entrada: n = 4, e = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Sortida: DFS del vèrtex 1 : 1 2 0 3
Explicació:
Diagrama DFS:



Exemple 1

Exemple 1

Entrada: n = 4, e = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Sortida: DFS del vèrtex 2 : 2 0 1 3
Explicació:
Diagrama DFS:

Exemple 2

Exemple 2

Pràctica recomanada DFS of Graph Prova-ho!

Com funciona DFS?

La cerca en profunditat és un algorisme per recórrer o cercar estructures de dades d'arbre o gràfic. L'algoritme comença al node arrel (seleccionant algun node arbitrari com a node arrel en el cas d'un gràfic) i explora el més lluny possible al llarg de cada branca abans de retrocedir.

Entenem el funcionament de Primera recerca en profunditat amb l'ajuda de la il·lustració següent:

Pas 1: Inicialment, la pila i les matrius visitades estan buides.

impressió java

La pila i les matrius visitades estan buides inicialment.

Pas 2: Visiteu 0 i poseu a la pila els seus nodes adjacents que encara no s'han visitat.

Visiteu el node 0 i poseu els seus nodes adjacents (1, 2, 3) a la pila

Pas 3: Ara, el node 1 a la part superior de la pila, així que visiteu el node 1 i feu-lo sortir de la pila i poseu tots els seus nodes adjacents que no es visiten a la pila.

Visita el node 1

Pas 4: Ara, Node 2 a la part superior de la pila, així que visiteu el node 2 i feu-lo sortir de la pila i poseu tots els seus nodes adjacents que no es visiten (és a dir, 3, 4) a la pila.

Visiteu el node 2 i poseu els seus nodes adjacents no visitats (3, 4) a la pila

Pas 5: Ara, el node 4 a la part superior de la pila, així que visiteu el node 4 i feu-lo sortir de la pila i poseu tots els seus nodes adjacents que no es visiten a la pila.

Visiteu el node 4

Pas 6: Ara, el node 3 a la part superior de la pila, així que visiteu el node 3 i feu-lo sortir de la pila i poseu tots els seus nodes adjacents que no es visiten a la pila.

Visiteu el node 3

Ara, Stack queda buit, el que significa que hem visitat tots els nodes i la nostra travessa DFS acaba.

A continuació es mostra la implementació de l'enfocament anterior:

C++


què és l'objecte 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>>visitat;> >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>>::iterador 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>

string convertir a int a Java 
>

>

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> 

>

>

Python 3




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

comanda arp 

>

>

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>>[en ];> >for> (>int> i = 0; i adj[i] = new List (); } // Funció per afegir una vora al gràfic void AddEdge(int v, int w) { // Afegeix w a la llista de v. adj[v].Afegir(w); } // Una funció utilitzada per DFS void DFSUtil(int v, bool[] visited) { // Marca el node actual com a visitat // i imprimeix-lo visitat[v] = true; Consola.Escriure(v + ' '); // Recorregut per a tots els vèrtexs // adjacents a aquesta llista de vèrtexs vList = adj[v]; foreach(var n a vList) { si (!visitat[n]) DFSUtil(n, visitat); } } // La funció per fer el recorregut DFS. // Utilitza DFSUtil() recursiu void DFS(int v) { // Marca tots els vèrtexs com a no visitats // (establert com a fals per defecte en c#) bool[] visited = new bool[V]; // Crida la funció d'ajuda recursiva // per imprimir el recorregut DFS DFSUtil(v, visitat); } // Codi del controlador 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( 'El següent és el primer recorregut de profunditat ' + '(a partir del vèrtex 2)'); // Crida a la funció g.DFS(2); Console.ReadKey(); } } // Aquest codi és aportat per techno2mahi>>> 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  // 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  
  
 
    
 
>
 
    
 
>
 
  Sortida  
 
Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>
 
 Anàlisi de complexitat de la profunditat Primera cerca: 
 
     
  •     Complexitat temporal:    O(V + E), on V és el nombre de vèrtexs i E és el nombre d'arestes del gràfic.
    •  
  •     Espai auxiliar:    O(V + E), ja que es requereix una matriu visitada addicional de mida V, i la mida de la pila per a la trucada iterativa a la funció DFS.
    •