logo

TechCodeview

Primera búsqueda en profundidad o DFS para un gráfico

Primer recorrido en profundidad (o DFS) para una gráfica es similar a Profundidad Primer recorrido de un árbol. El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos (un nodo puede ser visitado dos veces). Para evitar procesar un nodo más de una vez, utilice una matriz booleana visitada. Un gráfico puede tener más de un recorrido DFS.

Ejemplo:



Aporte: norte = 4, mi = 6
0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3
Producción: DFS desde el vértice 1: 1 2 0 3
Explicación:
Diagrama DFS:

Ejemplo 1

Ejemplo 1

Aporte: norte = 4, mi = 6
2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3
Producción: DFS desde el vértice 2: 2 0 1 3
Explicación:
Diagrama DFS:



Ejemplo 2

Ejemplo 2

Práctica recomendada DFS de Graph ¡Pruébelo!

¿Cómo funciona DFS?

La búsqueda en profundidad es un algoritmo para atravesar o buscar estructuras de datos de árboles o gráficos. El algoritmo comienza en el nodo raíz (seleccionando algún nodo arbitrario como nodo raíz en el caso de un gráfico) y explora lo más posible a lo largo de cada rama antes de retroceder.

Entendamos el funcionamiento de Primera búsqueda en profundidad con la ayuda de la siguiente ilustración:



Paso 1: Inicialmente, la pila y las matrices visitadas están vacías.

diferencia de fechas en excel

La pila y las matrices visitadas están vacías inicialmente.

Paso 2: Visite 0 y coloque sus nodos adyacentes que aún no han sido visitados en la pila.

Visite el nodo 0 y coloque sus nodos adyacentes (1, 2, 3) en la pila

Paso 3: Ahora, el nodo 1 está en la parte superior de la pila, así que visite el nodo 1, sáquelo de la pila y coloque todos los nodos adyacentes que no se visitan en la pila.

Visita el nodo 1

Etapa 4: Ahora, El nodo 2 está en la parte superior de la pila, así que visite el nodo 2, sáquelo de la pila y coloque todos sus nodos adyacentes que no sean visitados (es decir, 3, 4) en la pila.

Visite el nodo 2 y coloque sus nodos adyacentes no visitados (3, 4) en la pila

Paso 5: Ahora, el nodo 4 está en la parte superior de la pila, así que visite el nodo 4, sáquelo de la pila y coloque todos los nodos adyacentes que no se visitan en la pila.

Visita el nodo 4

Paso 6: Ahora, el nodo 3 está en la parte superior de la pila, así que visite el nodo 3, sáquelo de la pila y coloque todos los nodos adyacentes que no se visitan en la pila.

Visita el nodo 3

Ahora, la pila queda vacía, lo que significa que hemos visitado todos los nodos y nuestro recorrido DFS finaliza.

A continuación se muestra la implementación del enfoque anterior:

C++


c# fecha y hora



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

>

>

Java




conectarse a una base de datos 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> 

>

>

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> 

>

>

C#


cadena.formato en java



// 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ón para agregar un borde al gráfico void AddEdge(int v, int w) { // Agregar w a la lista de v. adj[v].Agregar(w); } // Una función utilizada por DFS void DFSUtil(int v, bool[] visitado) { // Marcar el nodo actual como visitado // e imprimirlo visitado[v] = true; Consola.Write(v + ' '); // Recurre para todos los vértices // adyacente a este vértice Lista vList = adj[v]; foreach(var n en vList) { if (!visited[n]) DFSUtil(n, visitado); } } // La función para realizar el recorrido DFS. // Utiliza DFSUtil() recursivo void DFS(int v) { // Marca todos los vértices como no visitados // (establecido como falso por defecto en c#) bool[] visitado = new bool[V]; // Llame a la función auxiliar recursiva // para imprimir el recorrido DFS DFSUtil(v, visitado); } // Código 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( 'Lo siguiente es el primer recorrido en profundidad ' + '(comenzando desde el vértice 2)'); // Llamada a función g.DFS(2); Consola.ReadKey(); } } // Este código es aportado por techno2mahi> 

>

>

delimitador java

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 

>

>

Producción 

Following is Depth First Traversal (starting from vertex 2) 2 0 1 3>

Análisis de complejidad de la primera búsqueda en profundidad:

  • Complejidad del tiempo: O (V + E), donde V es el número de vértices y E es el número de aristas del gráfico.
  • Espacio Auxiliar: O(V + E), ya que se requiere una matriz visitada adicional de tamaño V y el tamaño de la pila para la llamada iterativa a la función DFS.