algorithm - 各ノードでの訪問前と訪問後の深さ優先探索の反復

Question

誰かが私に反復深さ優先ツリートラバーサルの擬似コードを教えてもらえますか？そこでは、事前注文と事後注文の両方で各ノードに対してアクションを実行できますか？

つまり、ノードの子に適切な前のアクション、次に子からの上昇後のアクションですか？

また、私のツリーはバイナリではありません。各ノードには0..n個の子があります。

基本的に、私の場合は再帰的走査を変換します。ここでは、再帰のいずれかの側である現在のノードで、子への前操作と後操作を実行します。

Answer 1

私の計画は、2 つのスタックを使用することです。1 つはプレオーダー トラバーサル用で、もう 1 つはポストオーダー トラバーサル用です。ここで、標準の反復 DFS (深さ優先トラバーサル) を実行し、「前」スタックからすぐpopに「後」スタックにプッシュします。最後に、私の「投稿」スタックは、一番上に子ノードがあり、一番下にルートがあります。

treeSearch(Tree root) {
    Stack pre;
    Stack post;
    pre.add(root);
    while (pre.isNotEmpty()) {
        int x = pre.pop();
        // do pre-order visit here on x
        post.add(x);
        pre.addAll(getChildren(x));
    }
    while (post.isNotEmpty()) {
        int y = post.pop();
        // do post-order visit here on y
    }
}

rootpost最下部にとどまるため、スタックから常に最後にトラバースされます。

これは単純な Java コードです。

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
    }
}

これはツリーであると想定しているため、サイクルがなく、同じノードに再度アクセスする必要はありません。ただし、必要に応じて、常にアクセス済みの配列を取得し、それに対してチェックすることができます。

Answer 2

class Node:
  def __init__( self, value ):
    self.value    = value
    self.children = []

def preprocess( node ):
  print( node.value )

def postprocess( node ):
  print( node.value )

def preorder( root ):
  # Always a flat, homogeneous list of Node instances.
  queue = [ root ]
  while len( queue ) > 0:
    a_node = queue.pop( 0 )
    preprocess( a_node )
    queue = a_node.children + queue

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:
      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 )

Answer 3

お役に立てば幸いです。

http://www.vvlasov.com/2013/07/post-order-iterative-dfs-traversal.html

コード：

public void dfsPostOrderIterative(AdjGraph graph, AdjGraph.Node vertex, Callback callback) {
    Stack<Level> toVisit = new Stack<Level>();
    toVisit.push(new Level(Collections.singletonList(vertex)));

    while (!toVisit.isEmpty()) {
        Level level = toVisit.peek();

        if (level.index >= level.nodes.size()) {
            toVisit.pop();
            continue;
        }

        AdjGraph.Node node = level.nodes.get(level.index);

        if (!node.isVisited()) {
            if (node.isChildrenExplored()) {
                node.markVisited();
                callback.nodeVisited(graph, node);
                level.index++;
            } else {
                List<AdjGraph.Node> edges = graph.edges(node);
                List<AdjGraph.Node> outgoing = Lists.newArrayList(Collections2.filter(edges, new Predicate<AdjGraph.Node>() {
                    @Override
                    public boolean apply(AdjGraph.Node input) {
                        return !input.isChildrenExplored();
                    }
                }));

                if (outgoing.size() > 0)
                    toVisit.add(new Level(outgoing));
                node.markChildrenExplored();
            }
        } else {
            level.index++;
        }
    }
}

Answer 4

El Mariachiが提供するpostorder関数にpreProcessを挿入することで、必要なものが正確に揃ったと思います。

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 )