Profundidad no recursiva-Primera búsqueda (DFS) Uso de una pila

Question

Bien, esta es mi primera publicación en Desbordamiento de pila He estado leyendo durante un tiempo y realmente admiro el sitio. Espero que esto sea algo que sea aceptable preguntar. Así que he estado leyendo Intro to Algorithms (Cormen, MIT Press) todo el tiempo y estoy a la altura de los algoritmos de gráficos. He estado estudiando los algoritmos formales establecidos para la primera búsqueda de amplitud y profundidad con gran detalle.

Aquí es el pseudo-código dado para búsqueda en profundidad:

DFS(G) 
----------------------------------------------------------------------------------- 
1 for each vertex u ∈ G.V 
2  u.color ← WHITE  // paint all vertices white; undiscovered 
3  u.π ← NIL 
4  time ← 0    // global variable, timestamps 
5 for each vertex u ∈ G.V 
6  if u.color = WHITE 
7   DFS-VISIT(G,u) 

DFS-VISIT(G, u) 
----------------------------------------------------------------------------------- 
1 u.color ← GRAY   // grey u; it is discovered 
2 time ← time + 1 
3 u.d ← time 
4 for each v ∈ G.Adj[u] // explore edge (u,v) 
5  if v.color == WHITE 
6   v.π ← u 
7   DFS-VISIT(G,v) 
8 u.color ← BLACK   // blacken u; it is finished 
9 time ← time + 1 
10 u.f ← time 

Este algoritmo es recursiva y que procede de varias fuentes (será descubierto cada vértice en el gráfico sin conectar). Tiene varias propiedades que la mayoría de las implementaciones específicas del lenguaje pueden omitir. Se distingue entre 3 diferentes 'colores' de vértices. Inicialmente los pinta en blanco, luego cuando son 'descubiertos' (visitados en DFS-VISIT) se pintan de gris. El algoritmo DFS-VISIT ejecuta un bucle llamada recursivamente a sí mismo en la lista de adyacencia del vértice actual y solo pinta un vértice negro cuando no tiene más bordes a ningún nodo blanco.

También se mantienen otros dos atributos de cada vértice u.d y u.f son los sellos de tiempo para cuando se descubrió el vértice (pintado de gris) o cuando se terminó un vértice (pintado de negro). La primera vez que se pinta un nodo, tiene un sello de tiempo de uno y se incrementa al siguiente valor entero para cada vez que se pinta otro (ya sea gris o negro). u.π también se mantiene, que es solo un puntero al nodo desde el que se descubrió.

Algorithm Non-Recursive-DFS(G) 
----------------------------------------------------------------------------------- 
1 for each vertex u ∈ G.V 
2  u.color ← WHITE 
3  u.π ← NIL 
4 time = 0 
5 for each vertex u ∈ G.V 
6  if u.color = WHITE 
7   u.color ← GRAY 
8   time ← time + 1 
9   u.d ← time 
7   push(u, S) 
8   while stack S not empty 
9    u ← pop(S) 
10    for each vertex v ∈ G.Adj[u] 
11     if v.color = WHITE 
12      v.color = GRAY 
13      time ← time + 1 
14      v.d ← time 
15      v.π ← u 
16      push(v, S) 
17    u.color ← BLACK 
18    time ← time + 1 
19    u.f ← time 

* * EDITAR 31/10/12 Esto es embarazoso que mi algoritmo ha sido incorrecta durante tanto tiempo, que funcionaría en la mayoría de los casos, pero no todos. Acabo de recibir un distintivo de pregunta popular para la pregunta y vi dónde había visto Irfy el problema en su respuesta a continuación, así que ahí es donde va el mérito. Solo lo estoy arreglando aquí para cualquiera que necesite esto en el futuro.

¿Alguien ve una falla con el algoritmo anterior? No soy, con mucho, un experto en teoría de grafos, pero creo que tengo una buena comprensión de la recursión y la iteración y creo que esto debería funcionar de la misma manera. Estoy buscando hacerlo funcionalmente equivalente al algoritmo recursivo. Debe mantener todos los atributos del primer algoritmo, incluso si no son necesarios.

Cuando comencé a escribirlo no pensé que tendría un ciclo triple, pero así fue. He visto otros algoritmos iterativos cuando busqué en Google que solo tienen un bucle doblemente anidado, sin embargo, no parecen proceder de múltiples fuentes. (es decir, no descubrirán todos los vértices del gráfico no conectado)

Answer 1

Ambos algoritmos están bien. El segundo es una traducción directa de recursiva a basada en la pila. Todo el estado de mutación se almacena en la pila. G nunca cambia durante la ejecución del algoritmo.

Los algoritmos producirán un árbol de expansión para cada región desconectada, según el orden en que el algoritmo visitó cada nodo. Los árboles se representarán con referencias a los nodos padre (u.π) y como árboles de segmento (u.d y u.f).

Un elemento secundario tendrá una referencia a su nodo primario (o NULL si es una raíz), además de tener su rango (child.d .. child.f) dentro del rango de su padre.

parent.d < child.d < child.f < parent.f 

child.π = parent 

---

Editar: He encontrado un error en la traducción. En realidad, no está presionando el estado actual en la pila, sino un argumento de método futuro. Además, no está coloreando los nodos reventados GRAY y configurando el campo f.

Aquí es una reescritura del original primer algoritmo:

algorithm Stack-DFS(G) 
    for each vertex u ∈ G.V 
     u.color ← WHITE 
     u.π ← NIL 
    time ← 0 
    S ← empty stack 
    for each vertex u ∈ G.V 
     if u.color = WHITE 
      # Start of DFS-VISIT 
      step ← 1 
      index ← 0 
      loop unconditionally 
       if step = 1 
        # Before the loop 
        u.color ← GRAY 
        time ← time + 1 
        u.d ← time 
        step ← 2 
       if step = 2 
        # Start/continue looping 
        for each vertex v ∈ G.Adj[u] 
         i ← index of v 
         if i ≥ index and v.color = WHITE 
          v.π ← u 
          # Push current state 
          push((u, 2, i + 1), S) 
          # Update variables for new call 
          u = v 
          step ← 1 
          index ← 0 
          # Make the call 
          jump to start of unconditional loop 
        # No more adjacent white nodes 
        step ← 3 
       if step = 3 
        # After the loop 
        u.color ← BLACK 
        time ← time + 1 
        u.right ← time 
        # Return 
        if S is empty 
         break unconditional loop 
        else 
         u, step, index ← pop(S) 

Probablemente hay algunos lugares que podrían ser optimizados, pero debería al menos el trabajo ahora.

Resultado:

Name d f π 
q  1 16 NULL 
s  2 7 q 
v  3 6 s 
w  4 5 v 
t  8 15 q 
x  9 12 t 
z  10 11 x 
y  13 14 t 
r  17 20 NULL 
u  18 19 r 

Answer 2

Usted tiene un defecto grave en su código no recursivo.

Después de comprobar si v es WHITE, nunca se marcan que GRAY antes de empujar, por lo que puede ser visto como WHITE una y otra vez desde otros nodos no visitados, lo que resulta en múltiples referencias a ese nodo v desplaza a la pila. Esto es potencialmente un defecto catastrófico (podría causar bucles infinitos o similares).

Además, no establece .d a excepción de nodos raíz. Esto significa que los atributos Nested set model.d sy .f s no serán correctos. (Si no sabe qué son .d sy .f s, lea el artículo, fue muy esclarecedor para mí en aquellos días.del artículo left es su .d y right es su .f.)

su interior if básicamente tiene que ser el mismo que el exterior if menos los bucles, además de la referencia de los padres. Es decir:

11     if v.color = WHITE 
++      v.color ← GRAY 
++      time ← time + 1 
++      v.d ← time 
12      v.π ← u 
13      push(v, S) 

Corregir eso, y debe ser un verdadero equivalente.

Answer 3

Creo que hay al menos un caso en el que las versiones recursivas y la pila no son funcionalmente equivalentes. Considere el caso de un triángulo: vértices A, B y C conectados entre sí. Ahora, con el DFS recursivo, el gráfico predecesor que uno obtendría con la fuente A, sería A-> B-> C O A-> C-> B (A-> B implica que A es el padre de B en profundidad primer árbol).

Sin embargo, si utiliza la versión de pila de DFS, los padres de B y C siempre se registrarán como A. Nunca puede ser el caso de que el padre de B sea C o viceversa (que siempre es el caso de DFS recursivo). Esto es porque, al explorar la lista de adyacencia de cualquier vértice (aquí A), empujamos todos los miembros de la lista de adyacencia (aquí B y C) de una sola vez.

Esto puede volverse relevante si intenta usar DFS para buscar puntos de articulación en un gráfico [1]. Un ejemplo sería que la siguiente declaración es verdadera solo si usamos la versión recursiva de DFS.

Un vértice de la raíz es un punto de articulación si y sólo si tiene al menos dos niños en el primer árbol de profundidad.

En un triángulo, obviamente no hay punto de articulación, pero el stack-DFS todavía da dos hijos para cualquier vértice fuente en el árbol de profundidad (A tiene hijos B y C). Solo si creamos el primer árbol de profundidad usando DFS recursivo, la afirmación anterior es verdadera.

[1] Introducción a los algoritmos, CLRS - Problema 22-2 (Segunda y Tercera Edición)

Answer 4

En la versión no recursiva necesitamos otro color que refleja el estado de la pila recursiva. Entonces, agregaremos un color = ROJO para indicar que todos los elementos secundarios del nodo fueron empujados a la pila. También voy a asumir la pila tiene un método peek() (que de otro modo podría ser simulado con el pop y el impulso inmediato)

Entonces, con esto además de la versión actualizada del post original debe ser similar:

for each vertex u ∈ G.V 
     u.color ← WHITE 
     u.π ← NIL 
    time = 0 
    for each vertex u ∈ G.V 
     if u.color = WHITE 
      u.color ← GRAY 
      time ← time + 1 
      u.d ← time 
      push(u, S) 
      while stack S not empty 
       u ← peek(S) 
       if u.color = RED 
        //means seeing this again, time to finish 
        u.color ← BLACK 
        time ← time + 1 
        u.f ← time 
        pop(S) //discard the result 
       else 
        for each vertex v ∈ G.Adj[u] 
        if v.color = WHITE 
         v.color = GRAY 
         time ← time + 1 
         v.d ← time 
         v.π ← u 
         push(v, S) 
        u.color = RED 

Answer 5

I used Adjacency Matrix:  

void DFS(int current){ 
     for(int i=1; i<N; i++) visit_table[i]=false; 
     myStack.push(current); 
     cout << current << " "; 
     while(!myStack.empty()){ 
      current = myStack.top(); 
      for(int i=0; i<N; i++){ 
       if(AdjMatrix[current][i] == 1){ 
        if(visit_table[i] == false){ 
         myStack.push(i); 
         visit_table[i] = true; 
         cout << i << " "; 
        } 
        break; 
       } 
       else if(!myStack.empty()) 
        myStack.pop(); 
      } 
     } 
    } 

Answer 6

int stackk[100]; 
int top=-1; 
void graph::dfs(int v){ 
stackk[++top]=v; 
// visited[v]=1; 
while(top!=-1){ 
    int x=stackk[top--]; 
    if(!visited[x]) 
    {visited[x]=1; 
    cout<<x<<endl; 
    } 
    for(int i=V-1;i>=0;i--) 
    { 
     if(!visited[i]&&adj[x][i]) 
     { //visited[i]=1; 
      stackk[++top]=i; 
     } 
    } 
} 
} 
void graph::Dfs_Traversal(){ 
for(int i=0;i<V;i++) 
    visited[i]=0; 
for(int i=0;i<V;i++) 
    if(!visited[i]) 
    g.dfs(i); 

Answer 7

Aquí está el código en C++.

class Graph 
{ 
    int V;       // No. of vertices 
    list<int> *adj;     // Pointer to an array containing adjacency lists 
public: 
    Graph(int V);     // Constructor 
    void addEdge(int v, int w);    // function to add an edge to graph 
    void BFS(int s);     // prints BFS traversal from a given source s 
    void DFS(int s); 
}; 

Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; //list of V list 
} 

void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 


    void Graph::DFS(int s) 
     { 
       //mark unvisited to each node 
     bool *visited = new bool[V]; 
     for(int i = 0; i<V; i++) 
      visited[i] =false; 
     int *d = new int[V]; //discovery 
     int *f = new int[V]; //finish time 

     int t = 0;  //time 

     //now mark current node to visited 
     visited[s] =true; 
     d[s] = t;   //recored the discover time 

     list<int> stack; 

     list<int>::iterator i; 

     stack.push_front(s); 
     cout << s << " "; 

     while(!(stack.empty())) 
     { 
      s= stack.front(); 
      i = adj[s].begin(); 

      while ((visited[*i]) && (i != --adj[s].end())) 
      { 
       ++i; 
      } 
      while ((!visited[*i]) ) 
      { 

       visited[*i] =true; 
       t++; 
       d[*i] =t; 
       if (i != adj[s].end()) 
        stack.push_front(*i); 

       cout << *i << " "; 
       i = adj[*i].begin(); 

      } 

      s = stack.front(); 
      stack.pop_front(); 
      t++; 
      f[s] =t; 

     } 
     cout<<endl<<"discovery time of the nodes"<<endl; 

     for(int i = 0; i<V; i++) 
     { 
      cout<< i <<" ->"<< d[i] <<" "; 
     } 
     cout<<endl<<"finish time of the nodes"<<endl; 

     for(int i = 0; i<V; i++) 
     { 
      cout<< i <<" ->"<< f[i] <<" "; 
     } 

    } 

     int main() 
     { 
     // Create a graph given in the above diagram 
     Graph g(5); 
     g.addEdge(0, 1); 
     g.addEdge(0, 4); 
     g.addEdge(1, 4); 
     g.addEdge(1, 2); 
     g.addEdge(1, 3); 
     g.addEdge(3, 4); 
     g.addEdge(2, 3); 


     cout << endl<<"Following is Depth First Traversal (starting from vertex 0) \n"<<endl; 
     g.DFS(0); 

     return 0; 
    } 

Simple iterative DFS. También puede ver el tiempo de descubrimiento y finalización. Cualquier duda por favor comentar. He incluido suficientes comentarios para comprender el código.

Answer 8

Creo que logré escribir un pseudocódigo mucho más simple.

pero primero algunas observaciones para hacer las cosas un poco claro:

1. v.pDescendant - un puntero a un vértice descendiente dada por su lista de adyacencia.
2. en la lista de adyacencia, asumí que cada elemento tiene un campo "pNext" que apunta al siguiente elemento en la lista enlazada.
3. He utilizado alguna sintaxis C++, principalmente "->" y "&" para enfatizar qué es un puntero y qué no.
4. Stack.top() devuelve un puntero al primer elemento de la pila. pero a diferencia de pop(), no lo elimina.

El algoritmo se basa en la siguiente observación: se inserta un vértice en la pila cuando se visita. y eliminado (reventado) solo cuando terminamos de examinar (ennegrecer) a todos sus descendientes.

DFS(G) 
1. for all vertices v in G.V do 
2. v.color = WHITE; v.parent = NIL; v.d = NIL; v.f = NIL; v.pDescendant = adj[v].head 
3. time = 0 
4. Initialize Stack 
5. for all vertices v in G.V s.t. v.color == WHITE do 
6. time++ 
7. Stack.push(&v) 
8. v.color = GRAY 
9. v.d = time 
10. DFS-ITERATIVE(G,v) 

DFS-ITERATIVE(G,s) 
1. while Stack.Empty() == FALSE do 
2. u = Stack.top(); 
3. if u.pDescendant == NIL // no Descendants to u || no more vertices to explore 
4.  u.color = BLACK 
5.  time++ 
6.  u.f = time 
7.  Stack.pop() 
8. else if (u.pDescendant)->color == WHITE 
9.  Stack.push(u.pDescendant) 
10.  time++ 
10.  (u.pDescendant)->d = time 
11.  (u.pDescendant)->color = GRAY 
12.  (u.pDescendant)->parent = &u 
12.  u.pDescendant= (u.pDescendant)->pNext // point to next descendant on the adj list  
13. else 
14.  u.pDescendant= (u.pDescendant)->pNext // not sure about the necessity of this line