Non-récursive Depth-First Search (DFS) à l'Aide d'une Pile

Les deux algorithmes sont très bien. La seconde est une traduction directe de l'récursif à la fonction de pile. Tous la mutation de l'état sont stockées dans la pile. G ne change jamais au cours de l'exécution de l'algorithme.

Les algorithmes de produire un spanning tree pour chaque déconnecté de la région, basé sur l'ordre de l'algorithme visité chaque nœud. Les arbres seront représentées à la fois les références à la mère-nœuds (u.π), et que le segment des arbres (u.d et u.f).

De l'enfant est une référence à son nœud parent (ou NULL si c'est une racine), ainsi que d'avoir la gamme (child.d .. child.f) contenue à l'intérieur de son parent.

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

child.π = parent

Edit: j'ai trouvé une erreur dans la traduction. Vous n'êtes pas réellement pousse l'état actuel dans la pile, mais un avenir argument de méthode. En outre, vous n'êtes pas la coloration de l'sauté nœuds GRAY et le réglage de la f champ.

Ici est une réécriture de l'origine première de l'algorithme:

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)

Il y a probablement quelques endroits qui pourraient être optimisés, mais devrait au moins fonctionner maintenant.

Résultat:

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

OriginalL'auteur Markus Jarderot

Je pense que j'ai réussi à écrire un beaucoup plus simple de pseudo-code.

mais d'abord, quelques remarques à faire des choses un peu clair:

1. v. pDescendant - un pointeur vers un sommet descendant par sa liste d'adjacence.
2. dans la liste d'adjacence, j'ai supposé que chaque élément a un champ "pNext" qui pointe vers l'élément suivant sur la liste chaînée.
3. J'ai utilisé une syntaxe C++, principalement "->" et "&" pour insister sur ce qu'est un pointeur et ce qui ne l'est pas.
4. De la pile.top() renvoie un pointeur sur le premier élément de la pile. mais à la différence de la pop(), il ne le supprime pas.

L'algorithme est basé sur l'observation suivante:
un sommet est poussé sur la pile lors de la visite. et supprimés (sauté) seulement lorsque nous aurons terminé l'examen (noircissement) de toutes ses descendants.

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      

OriginalL'auteur

Vous avez un grave défaut dans votre non-récursive code.

Après vous vérifiez si v est WHITE, vous ne marquera jamais il GRAY avant de le pousser, de sorte qu'il peut être considéré comme WHITE encore et encore, d'autres non visités nœuds, résultant de multiples références à la v nœud poussé à la pile. C'est potentiellement catastrophique faille (pouvant provoquer une boucle infinie ou tel).

Aussi, vous ne définissez pas .d sauf pour les nœuds racine. Cela signifie que le Ensemble imbriqué modèle attributs .ds et .fs n'est pas correct. (Si vous ne savez pas ce .ds et .fs sont, à la lecture de cet article, il a été très instructif pour moi à l'époque. L'article left est votre .d et right est votre .f.)

Votre intérieur if fondamentalement doit être le même que l'extérieur if moins les boucles, plus le parent de référence. Qui est:

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

Les corriger, et ce doit être un vrai équivalent.

OriginalL'auteur Irfy

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();
            }
        }
    }

OriginalL'auteur noDispName