Cómo implementar la primera búsqueda de profundidad para el gráfico con una aproximación no recursiva

Bueno, he dedicado mucho tiempo a este tema. Sin embargo, solo puedo encontrar soluciones con métodos no recursivos para un árbol: no recursivo para árbol , o método recursivo para el gráfico, Recursivo para gráfico .

Y muchos tutoriales (no proporciono esos enlaces aquí) tampoco proporcionan los enfoques. O el tutorial es totalmente incorrecto. Por favor, ayúdame.

Actualizado:

Es realmente difícil de describir:

Si tengo un gráfico no dirigido:

1 / | \ 4 | 2 3 / 

1– 2– 3 –1 es un ciclo.

En el paso: push the neighbors of the popped vertex into the stack

WHAT'S THE ORDER OF THE VERTEXES SHOULD BE PUSHED?

Si el orden de empuje es 2 4 3, el vértice en la stack es:

 | | |3| |4| |2| _ 

Después de hacer estallar los nodos, obtuvimos el resultado: 1 -> 3 -> 4 -> 2 en lugar de 1 -> 3 -> 2 -> 4.

ES INCORRECTO ¿QUÉ CONDICIÓN DEBO AGREGAR PARA DETENER ESTE ESCENARIO?

Un DFS sin recursión es básicamente lo mismo que BFS , pero usa una stack en lugar de una cola como estructura de datos.

El hilo Iterative DFS vs Recursive DFS y los diferentes elementos ordenados se manejan con ambos enfoques y la diferencia entre ellos (¡y hay! ¡No recorrerás los nodos en el mismo orden!)

El algoritmo para el enfoque iterativo es básicamente:

 DFS(source): s <- new stack visited <- {} // empty set s.push(source) while (s is not empty): current <- s.pop() if (current is in visited): continue visited.add(current) // do something with current for each node v such that (current,v) is an edge: s.push(v) 

Esta no es una respuesta, sino un comentario extendido, que muestra la aplicación del algoritmo en la respuesta de @ amit al gráfico en la versión actual de la pregunta, suponiendo que 1 es el nodo de inicio y sus vecinos son empujados en el orden 2, 4, 3:

  1 / | \ 4 | 2 3 / Actions Stack Visited ======= ===== ======= push 1 [1] {} pop and visit 1 [] {1} push 2, 4, 3 [2, 4, 3] {1} pop and visit 3 [2, 4] {1, 3} push 1, 2 [2, 4, 1, 2] {1, 3} pop and visit 2 [2, 4, 1] {1, 3, 2} push 1, 3 [2, 4, 1, 1, 3] {1, 3, 2} pop 3 (visited) [2, 4, 1, 1] {1, 3, 2} pop 1 (visited) [2, 4, 1] {1, 3, 2} pop 1 (visited) [2, 4] {1, 3, 2} pop and visit 4 [2] {1, 3, 2, 4} push 1 [2, 1] {1, 3, 2, 4} pop 1 (visited) [2] {1, 3, 2, 4} pop 2 (visited) [] {1, 3, 2, 4} 

Por lo tanto, la aplicación del algoritmo empujando a los vecinos 1 en el orden 2, 4, 3 da como resultado la orden de visita 1, 3, 2, 4. Independientemente de la orden de inserción para los vecinos de 1, 2 y 3 serán adyacentes en la orden de visita porque cualquiera que sea visitado primero empujará al otro, que todavía no se ha visitado, y al 1 que se ha visitado.

La lógica DFS debe ser:

1) si no se visita el nodo actual, visite el nodo y márquelo como visitado
2) para todos sus vecinos que no han sido visitados, empújelos a la stack

Por ejemplo, definamos una clase GraphNode en Java:

 class GraphNode { int index; ArrayList neighbors; } 

y aquí está el DFS sin recursión:

 void dfs(GraphNode node) { // sanity check if (node == null) { return; } // use a hash set to mark visited nodes Set set = new HashSet(); // use a stack to help depth-first traversal Stack stack = new Stack(); stack.push(node); while (!stack.isEmpty()) { GraphNode curr = stack.pop(); // current node has not been visited yet if (!set.contains(curr)) { // visit the node // ... // mark it as visited set.add(curr); } for (int i = 0; i < curr.neighbors.size(); i++) { GraphNode neighbor = curr.neighbors.get(i); // this neighbor has not been visited yet if (!set.contains(neighbor)) { stack.push(neighbor); } } } } 

Podemos usar la misma lógica para hacer DFS recursivamente, clonar gráfico, etc.

La recursión es una forma de usar la stack de llamadas para almacenar el estado del recorrido del gráfico. Puede usar la stack explícitamente, digamos teniendo una variable local de tipo std::stack , entonces no necesitará la recursión para implementar el DFS, sino simplemente un bucle.

bueno. si todavía estás buscando un código java

 dfs(Vertex start){ Stack stack = new Stack<>(); // initialize a stack List visited = new ArrayList<>();//maintains order of visited nodes stack.push(start); // push the start while(!stack.isEmpty()){ //check if stack is empty Vertex popped = stack.pop(); // pop the top of the stack if(!visited.contains(popped)){ //backtrack if the vertex is already visited visited.add(popped); //mark it as visited as it is not yet visited for(Vertex adjacent: popped.getAdjacents()){ //get the adjacents of the vertex as add them to the stack stack.add(adjacent); } } } for(Vertex v1 : visited){ System.out.println(v1.getId()); } } 

Código de Python La complejidad del tiempo es O ( V + E ) donde V y E son el número de vértices y bordes, respectivamente. La complejidad del espacio es O ( V ) debido al peor de los casos donde hay una ruta que contiene cada vértice sin ningún retroceso (es decir, la ruta de búsqueda es una cadena lineal ).

La stack almacena tuplas de la forma (vértice, vertex_edge_index) para que el DFS se pueda reanudar desde un vértice particular en el borde inmediatamente posterior al último borde procesado desde ese vértice (al igual que la stack de llamadas a función de un DFS recursivo).

El código de ejemplo usa un dígrafo completo en el que cada vértice está conectado a cada otro vértice. Por lo tanto, no es necesario almacenar una lista de bordes explícita para cada nodo, ya que el gráfico es una lista de bordes (el gráfico G contiene todos los vértices).

 numv = 1000 print('vertices =', numv) G = [Vertex(i) for i in range(numv)] def dfs(source): s = [] visited = set() s.append((source,None)) time = 1 space = 0 while s: time += 1 current, index = s.pop() if index is None: visited.add(current) index = 0 # vertex has all edges possible: G is a complete graph while index < len(G) and G[index] in visited: index += 1 if index < len(G): s.append((current,index+1)) s.append((G[index], None)) space = max(space, len(s)) print('time =', time, '\nspace =', space) dfs(G[0]) 

Salida:

 time = 2000 space = 1000 

Tenga en cuenta que el tiempo aquí mide las operaciones V y no E. El valor es numv * 2 porque cada vértice se considera dos veces, una vez en el descubrimiento y una vez al terminar.

Acutally, stack no es capaz de lidiar con el tiempo de descubrimiento y finalización, si queremos implementar DFS con stack, y queremos tratar con descubrir el tiempo y la hora de finalización, tendríamos que recurrir a otra stack de grabadora, se muestra mi implementación a continuación, haga que la prueba sea correcta, a continuación se muestra el caso-1, caso-2 y caso-3 gráfico.

caso 1 case-2 caso-3

 from collections import defaultdict class Graph(object): adj_list = defaultdict(list) def __init__(self, V): self.V = V def add_edge(self,u,v): self.adj_list[u].append(v) def DFS(self): visited = [] instack = [] disc = [] fini = [] for t in range(self.V): visited.append(0) disc.append(0) fini.append(0) instack.append(0) time = 0 for u_ in range(self.V): if (visited[u_] != 1): stack = [] stack_recorder = [] stack.append(u_) while stack: u = stack.pop() visited[u] = 1 time+=1 disc[u] = time print(u) stack_recorder.append(u) flag = 0 for v in self.adj_list[u]: if (visited[v] != 1): flag = 1 if instack[v]==0: stack.append(v) instack[v]= 1 if flag == 0: time+=1 temp = stack_recorder.pop() fini[temp] = time while stack_recorder: temp = stack_recorder.pop() time+=1 fini[temp] = time print(disc) print(fini) if __name__ == '__main__': V = 6 G = Graph(V) #============================================================================== # #for case 1 # G.add_edge(0,1) # G.add_edge(0,2) # G.add_edge(1,3) # G.add_edge(2,1) # G.add_edge(3,2) #============================================================================== #============================================================================== # #for case 2 # G.add_edge(0,1) # G.add_edge(0,2) # G.add_edge(1,3) # G.add_edge(3,2) #============================================================================== #for case 3 G.add_edge(0,3) G.add_edge(0,1) G.add_edge(1,4) G.add_edge(2,4) G.add_edge(2,5) G.add_edge(3,1) G.add_edge(4,3) G.add_edge(5,5) G.DFS() 

Creo que necesita usar una matriz booleana visited[n] para verificar si el nodo actual se visita o no antes.

Un algoritmo recursivo funciona muy bien para DFS cuando intentamos sumergirnos lo más profundo posible, es decir. tan pronto como encontremos un vértice no explorado, vamos a explorar su PRIMER vecino no explorado de inmediato. Debes BREAK fuera del ciclo for tan pronto como encuentres el primer vecino no explorado.

 for each neighbor w of v if w is not explored mark w as explored push w onto the stack BREAK out of the for loop 

Creo que este es un DFS optimizado con respecto al espacio correcto si estoy equivocado.

 s = stack s.push(initial node) add initial node to visited while s is not empty: v = s.peek() if for all E(v,u) there is one unvisited u: mark u as visited s.push(u) else s.pop 

Usando Stack e implementando como lo hizo la stack de llamadas en el proceso de recursión-

La idea es empujar un vértice en la stack, y luego empujar su vértice adyacente a él que está almacenado en una lista de adyacencia en el índice del vértice y luego continuar este proceso hasta que no podamos avanzar más en el gráfico, ahora si no podemos avanzar en el gráfico, luego eliminaremos el vértice que se encuentra actualmente en la parte superior de la stack, ya que no puede llevarnos a ningún vértice que no se haya visitado.

Ahora, al usar stack, nos ocupamos del punto de que el vértice solo se elimina de la stack cuando se han visitado todos los vértices que se pueden explorar desde el vértice actual, lo que el proceso de recursión estaba haciendo automáticamente.

por ejemplo,

Vea el gráfico de ejemplo aquí.

(0 (1 (2 (4 4) 2) (3 3) 1) 0) (6 (5 5) (7 7) 6)

El paréntesis anterior muestra el orden en que se agrega el vértice en la stack y se elimina de la stack, por lo que un paréntesis para un vértice se cierra solo cuando se hayan realizado todos los vértices que se pueden visitar.

(Aquí he utilizado la representación de la Lista de adyacencia y la he implementado como un vector de lista (vector> AdjList) usando C ++ STL)

 void DFSUsingStack() { /// we keep a check of the vertices visited, the vector is set to false for all vertices initially. vector visited(AdjList.size(), false); stack st; for(int i=0 ; i :: iterator it = AdjList[curr].begin() ; it != AdjList[curr].end() ; it++){ if(visited[*it] == false){ st.push(*it); cout << (*it) << '\n'; visited[*it] = true; break; } } /// We can move ahead from current only if a new vertex has been added on the top of the stack. if(st.top() != curr){ continue; } st.pop(); } } } 

El siguiente código Java será útil:

 private void DFS(int v,boolean[] visited){ visited[v]=true; Stack S = new Stack(); S.push(v); while(!S.isEmpty()){ int v1=S.pop(); System.out.println(adjLists.get(v1).name); for(Neighbor nbr=adjLists.get(v1).adjList; nbr != null; nbr=nbr.next){ if (!visited[nbr.VertexNum]){ visited[nbr.VertexNum]=true; S.push(nbr.VertexNum); } } } } public void dfs() { boolean[] visited = new boolean[adjLists.size()]; for (int v=0; v < visited.length; v++) { if (!visited[v])/*This condition is for Unconnected Vertices*/ { System.out.println("\nSTARTING AT " + adjLists.get(v).name); DFS(v, visited); } } } 

Mucha gente dirá que el DFS no recursivo es solo BFS con una stack en lugar de una cola. Eso no es exacto, déjame explicarte un poco más.

DFS recursivo

El DFS recursivo usa la stack de llamadas para mantener el estado, lo que significa que usted no administra una stack separada usted mismo.

Sin embargo, para un gráfico grande, el DFS recursivo (o cualquier función recursiva) puede dar como resultado una recursión profunda, que puede bloquear su problema con un desbordamiento de stack (no este sitio web, el real ).

DFS no recursivo

DFS no es lo mismo que BFS. Tiene una utilización de espacio diferente, pero si lo implementa como BFS, pero usando una stack en lugar de una cola, usará más espacio que el DFS no recursivo.

¿Por qué más espacio?

Considera esto:

 // From non-recursive "DFS" for (auto i&: adjacent) { if (!visited(i)) { stack.push(i); } } 

Y compáralo con esto:

 // From recursive DFS for (auto i&: adjacent) { if (!visited(i)) { dfs(i); } } 

En la primera parte del código, está colocando todos los nodos adyacentes en la stack antes de iterar al siguiente vértice adyacente y eso tiene un costo de espacio. Si el gráfico es grande, puede marcar una diferencia significativa.

Que hacer entonces?

Si decide resolver el problema de espacio iterando sobre la lista de adyacencia nuevamente después de abrir la stack, eso agregará un costo de complejidad de tiempo.

Una solución es agregar elementos a la stack uno por uno, a medida que los visita. Para lograr esto, puede guardar un iterador en la stack para reanudar la iteración después de hacer estallar.

Camino flojo

En C / C ++, un enfoque perezoso es comstackr su progtwig con un tamaño de stack más grande y boost el tamaño de la stack a través de ulimit , pero eso es realmente pésimo. En Java, puede establecer el tamaño de la stack como un parámetro de JVM.