El primer recorrido en profundidad (o DFS) para un gráfico es similar a Profundidad del 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
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
Recomendado: Resuélvelo en PRÁCTICA primero, antes de pasar a la solución.
¿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.
A continuación se muestra la implementación del enfoque anterior:
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> |
>
>Producción
árbol binario vs árbol de búsqueda binaria
Following is Depth First Traversal (starting from vertex 2): 2 0 1 3>
Complejidad del tiempo: O(V+E) donde V es el número de vértices en el gráfico y E es el número de aristas
Espacio Auxiliar: O(V+E)
Consulte el artículo completo sobre Primera búsqueda en profundidad o DFS para un gráfico ¡para más detalles!