Depth-First Search (DFS) non ricorsivo utilizzando uno stack

Question

Ok questo è il mio primo post su Stack Overflow che sto leggendo da un po 'e ammiro davvero il sito. Spero che questo sia qualcosa che sarà accettabile da chiedere. Quindi ho letto gli Intro to Algorithms (Cormen. MIT Press) fino in fondo e sono all'altezza degli algoritmi del grafico. Ho studiato gli algoritmi formali predisposti per l'ampiezza e la profondità per la prima ricerca con dettagli molto precisi.

Ecco il pseudo-codice dato per la ricerca in profondità:

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 

Questo algoritmo è ricorsiva e procede da più fonti (si scoperto ogni vertice nel grafico non collegato). Ha diverse proprietà che la maggior parte delle implementazioni linguistiche potrebbero tralasciare. Distingue tra 3 diversi "colori" di vertici. Dipinge inizialmente tutti di bianco, poi quando vengono "scoperti" (visitati in DFS-VISIT) vengono poi dipinti in grigio. L'algoritmo DFS-VISIT esegue un ciclo ricorsivamente chiamandosi nell'elenco di adiacenza del vertice corrente e dipinge solo un vertice nero quando non ha più bordi su alcun nodo bianco.

Anche due altri attributi di ciascun vertice vengono mantenuti u.d e u.f sono i timestamp di quando il vertice è stato scoperto (verniciato grigio) o quando un vertice è finito (verniciato nero). La prima volta che viene dipinto un nodo ha un timestamp di uno e viene incrementato al successivo valore intero per ogni volta che viene dipinto un altro (sia esso grigio o nero). viene mantenuto anche u.π che è solo un puntatore al nodo da cui è stato scoperto.

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 

* EDIT * 10/31/12 Questo è imbarazzante che il mio algoritmo è stato corretto per così tanto tempo, che avrebbe funzionato nella maggior parte dei casi, ma non tutti. Ho appena ricevuto un distintivo di domanda popolare per la domanda e ho visto dove Irfy aveva individuato il problema nella sua risposta qui sotto, quindi è qui che va il merito. Sto solo aggiustandolo qui per chiunque ne abbia bisogno in futuro.

Qualcuno vede un difetto con l'algoritmo di cui sopra? Non sono un esperto di teoria dei grafi, ma penso di avere una buona conoscenza della ricorsione e dell'iterazione e credo che questo dovrebbe funzionare allo stesso modo. Sto cercando di renderlo funzionalmente equivalente all'algoritmo ricorsivo. Dovrebbe mantenere tutti gli attributi del primo algoritmo anche se non sono necessari.

Quando ho iniziato a scrivere, non pensavo che avrei avuto un triplo loop, ma è andata così. Ho visto altri algoritmi iterativi quando ho cercato su Google che aveva solo un ciclo doppiamente annidato, tuttavia, non sembra provenire da più fonti. (cioè non scopriranno ogni vertice del grafico non connesso)

Answer 1

Entrambi gli algoritmi sono soddisfacenti. Il secondo è una traduzione diretta da ricorsiva a stack-based. Tutti gli stati di mutazione sono memorizzati nello stack. G non cambia mai durante l'esecuzione dell'algoritmo.

Gli algoritmi generano uno spanning tree per ogni area sconnessa, in base all'ordine in cui l'algoritmo ha visitato ciascun nodo. Gli alberi saranno rappresentati sia con riferimenti ai nodi parent (u.π), sia come segmenti di alberi (u.d e u.f).

Un figlio avrà un riferimento al suo nodo genitore (o NULL se è una radice), oltre ad avere il suo intervallo (child.d .. child.f) contenuto all'interno del raggio genitore.

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

child.π = parent 

---

Edit: Ho trovato un errore nella traduzione. In realtà non stai spingendo lo stato corrente nello stack, ma un argomento del futuro metodo. Inoltre, non si colorano i nodi spuntati GRAY e si imposta il campo f.

Ecco una riscrittura del primo algoritmo originale:

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) 

C'è probabilmente un paio di posti che potrebbero essere ottimizzati, ma dovrebbe almeno lavoro ora.

Risultato:

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

Hai un difetto grave nel tuo codice non ricorsivo.

Dopo aver controllato se v è WHITE, non hai mai segnarlo GRAY prima di spingere, quindi potrebbe essere visto come WHITE più e più volte da altri nodi non visitati, con conseguente molteplici riferimenti a tale v nodo inserito nello stack. Questo è potenzialmente un difetto catastrofico (potrebbe causare loop infiniti o simili).

Inoltre, non impostare .d eccetto per i nodi radice. Ciò significa che gli attributi .d e .f s non saranno corretti. (Se non sai cosa sono gli .d se .f s, leggi l'articolo, è stato molto illuminante per me nei giorni passati.L'articolo left è il tuo .d e right è il vostro .f.)

vostro interno if deve fondamentalmente per essere lo stesso di quello esterno if meno loop, più il genitore di riferimento. Ovvero:

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

Correggilo, e dovrebbe essere un vero equivalente.

Answer 3

Credo che ci sia almeno un caso in cui le versioni ricorsive e dello stack non sono funzionalmente equivalenti. Considera il caso di un triangolo: i vertici A, B e C sono collegati tra loro. Ora, con il DFS ricorsivo, il grafico predecessore che si otterrebbe con la sorgente A, sarebbe A-> B-> C OR A-> C-> B (A-> B implica A è il genitore di B in profondità primo albero).

Tuttavia, se si utilizza la versione stack di DFS, i genitori di entrambi B e C, verrebbero sempre registrati come A. Non può mai essere il caso che genitore di B sia C o viceversa (che è sempre il caso per DFS ricorsivo). Questo perché, quando si esplora la lista di adiacenza di qualsiasi vertice (qui A), si inseriscono tutti i membri della lista di adiacenza (qui B e C) in una volta.

Questo può diventare rilevante se si tenta di utilizzare DFS per trovare i punti di articolazione in un grafico [1]. Un esempio potrebbe essere che la seguente dichiarazione è valida solo se si utilizza la versione ricorsiva di DFS.

Un vertice di radice è un punto di articolazione se e solo se ha almeno due figli nel primo albero di profondità.

In un triangolo, non vi è ovviamente alcun punto di articolazione, ma lo stack-DFS fornisce ancora due bambini per qualsiasi vertice sorgente nell'albero depth-first (A ha figli B e C). È solo se creiamo il primo albero di profondità utilizzando DFS ricorsivo che l'affermazione precedente è vera.

[1] Introduzione agli algoritmi, CLRS - Problema 22-2 (seconda e terza edizione)

Answer 4

Nella versione non ricorsiva abbiamo bisogno di un altro colore che riflette lo stato della pila ricorsiva. Quindi, aggiungeremo un colore = ROSSO per indicare che tutti i figli del nodo sono stati inseriti nello stack. Vorrei anche assumere la pila ha un metodo peek() (che altrimenti potrebbe essere simulato con il pop e spingere immediato)

Così, con quella aggiunta la versione aggiornata del post originale dovrebbe essere simile:

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

Ecco il codice in 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; 
    } 

Semplice DFS iterativo. Puoi anche vedere il tempo di scoperta e l'ora di fine. Qualsiasi dubbio si prega di commentare. Ho incluso commenti sufficienti per capire il codice.

Answer 8

Penso di essere riuscito a scrivere uno pseudo-codice molto più semplice.

ma prima un paio di osservazioni per rendere le cose un po 'chiara:

1. v.pDescendant - un puntatore ad un vertice discendente data dalla sua lista di adiacenza.
2. nell'elenco di adiacenza, ho assunto che ogni elemento abbia un campo "pNext" che punta all'elemento successivo nell'elenco collegato.
3. Ho usato una certa sintassi C++, principalmente "->" e "&" per enfatizzare cosa è un puntatore e cosa no.
4. Stack.top() restituisce un puntatore al primo elemento della pila. ma a differenza di pop(), non lo rimuove.

L'algoritmo si basa sulla seguente osservazione: un vertice viene inserito nello stack quando visitato. e rimosso (spuntato) solo quando abbiamo finito di esaminare (annerire) tutti i suoi discendenti.

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