Je pense que j'ai exactement ce dont j'ai besoin en insérant une préprocession dans la fonction Postard Food de El Mariachi:

def postorder( root ):
 # Always a flat, homogeneous list of Node instances:
 queue   = [ root ]
 visited = set()
 while len( queue ) > 0:
   a_node = queue.pop( 0 )
   if a_node not in visited:
     preprocess( a_node )                  # <<<<<<<< Inserted
     visited.add( a_node )
     queue = a_node.children + [ a_node ] + queue
   else:
     # this is either a leaf or a parent whose children have all been processed
     postprocess( a_node )

J'espère que vous le trouverez utile.

http://www.vvlasov.com/ 2013/07 / post-commander-itératif-dfs-trersal.html

code: xxx

Je me rends compte que ce post a plusieurs années, mais aucune des réponses ne semble répondre directement à la question, alors j'ai pensé que j'écris quelque chose d'un peu simple.

Ceci suppose un graphique indexé entier; Mais vous pouvez certainement l'adapter si nécessaire. La clé de faire des DFS itérativement et d'avoir des opérations pré-commandes / post-commandes consiste à ne pas simplement ajouter tous les enfants em> tous les em> se comporter exactement comme des DFs récursifs, qui ajoute un enfant qui ajoute un enfant -node à la pile à la fois et ne les retirez que de la pile une fois qu'elle est terminée. Je l'accomplie dans mon exemple en créant un nœud wrapper avec la liste des adjacents comme une pile. Juste omettre le chèque de cycle si vous souhaitez autoriser des cycles (il ne traverse pas de nœuds visités de toute façon, cela fonctionnera toujours) P>

class Stack(object):
    def __init__(self, l=None):
        if l is None:
            self._l = []
        else:
            self._l = l
        return

    def pop(self):
        return self._l.pop()

    def peek(self):
        return self._l[-1]

    def push(self, value):
        self._l.append(value)
        return

    def __len__(self):
        return len(self._l)

class NodeWrapper(object):
    def __init__(self, graph, v):
        self.v = v
        self.children = Stack(graph[v])
        return

def iterative_postorder(G, s):
    onstack = [False] * len(G)
    edgeto = [None] * len(G)
    visited = [False] * len(G)

    st = Stack()
    st.push(NodeWrapper(G, s))

    while len(st) > 0:
        vnode = st.peek()
        v = vnode.v
        if not onstack[v]:
            print "Starting %d" % (v)
        visited[v] = True
        onstack[v] = True
        if len(vnode.children) > 0:
            e = vnode.children.pop()
            if onstack[e]:
                cycle = [e]
                e = v
                while e != cycle[0]:
                    cycle.append(e)
                    e = edgeto[e]
                raise StandardError("cycle detected: %s, graph not acyclic" % (cycle))
            if not visited[e]:
                edgeto[e] = v
                st.push(NodeWrapper(G, e))
        else:
            vnode = st.pop()
            onstack[vnode.v] = False
            print 'Completed %d' % (vnode.v)

Mon plan est d'utiliser deux piles. Un pour une traversée de pré-commande et un autre est pour une traversée post-commande. Maintenant, j'exécute une standard itérative DFS (Profond-première traversée), et dès que je POP code> de la pile "Pre" Je le pousse dans la pile "Post". À la fin, ma pile "post" aura un nœud enfant en haut et et une racine en bas.

public void treeSearch(Tree tree) {
    Stack<Integer> preStack = new Stack<Integer>();
    Stack<Integer> postStack = new Stack<Integer>();
    preStack.add(tree.root);
    while (!preStack.isEmpty()) {
        int currentNode = preStack.pop();
        // do pre-order visit on current node
        postStack.add(currentNode);
        int[] children = tree.getNeighbours(currentNode);
        for (int child : children) {
            preStack.add(child);
        }
    }

    while (!postStack.isEmpty()) {
        int currentNode = postStack.pop();
        // do post-order visit on current node
    }
}

Une simple implémentation de python avec deux visiteurs différents xxx

Solution itérative pour les graphiques non-arbores

Après une expérience sans succès avec différentes solutions, permettez-moi d'ajouter de pseudocode pour une solution itérative dans laquelle vous recréez essentiellement l'espace de pile d'appel de fonction (qui pourrait déborder dans une version récursive) dans une variable de pile .

Tout l'état que vous devez stocker est le numéro Vertex Number et le nombre de voisins déjà traitées . Cela peut être un tuple, une liste, un objet, quelle que soit votre langue le permet.

L'avantage de cette solution est que vous n'obtenez pas trop de pile, cela fonctionne également pour les graphiques ayant des cycles < / fort> et c'est assez robuste. Obtenir le prochain voisin est facile si vous utilisez une liste d'adjacence ou une matrice.

C'est pseudocode car il est plus facile de comprendre et vous ne copieriez pas simplement le code de cela, n'est-ce pas? < Pré> xxx