algorithm - problemas - Cómo implementar la primera búsqueda de profundidad para el gráfico con una aproximación no recursiva
profundidad iterativa inteligencia artificial (13)
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 pila 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?
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 pila 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.
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()
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 pila 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 pila 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.
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
Creo que necesita usar una matriz booleana visited[n] para verificar si el nodo actual se visita o no antes.
El siguiente código Java será útil:
private void DFS(int v,boolean[] visited){
visited[v]=true;
Stack<Integer> S = new Stack<Integer>();
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);
}
}
}
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 pila
Por ejemplo, definamos una clase GraphNode en Java:
class GraphNode {
int index;
ArrayList<GraphNode> 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<GraphNode> set = new HashSet<GraphNode>();
// use a stack to help depth-first traversal
Stack<GraphNode> stack = new Stack<GraphNode>();
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 pila de llamadas para almacenar el estado del recorrido del gráfico. Puede usar la pila 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.
Mucha gente dirá que el DFS no recursivo es solo BFS con una pila en lugar de una cola. Eso no es exacto, déjame explicarte un poco más.
DFS recursivo
El DFS recursivo usa la pila de llamadas para mantener el estado, lo que significa que usted no administra una pila 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 pila (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 pila 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 pila 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 pila, eso agregará un costo de complejidad de tiempo.
Una solución es agregar elementos a la pila uno por uno, a medida que los visita. Para lograr esto, puede guardar un iterador en la pila para reanudar la iteración después de hacer estallar.
Camino flojo
En C / C ++, un enfoque perezoso es compilar su programa con un tamaño de pila más grande y aumentar el tamaño de la pila a través de ulimit , pero eso es realmente pésimo. En Java, puede establecer el tamaño de la pila como un parámetro de JVM.
Un DFS sin recursión es básicamente lo mismo que BFS , pero usa una stack 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)
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
bueno. si todavía estás buscando un código java
dfs(Vertex start){
Stack<Vertex> stack = new Stack<>(); // initialize a stack
List<Vertex> 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());
}
}
Usando Stack e implementando como lo hizo la pila de llamadas en el proceso de recursión-
La idea es empujar un vértice en la pila, 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 pila, 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 pila 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.
(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 pila y se elimina de la pila, 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<bool> visited(AdjList.size(), false);
stack<int> st;
for(int i=0 ; i<AdjList.size() ; i++){
if(visited[i] == true){
continue;
}
st.push(i);
cout << i << ''/n'';
visited[i] = true;
while(!st.empty()){
int curr = st.top();
for(list<int> :: 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();
}
}
}