非递归深度优先搜索算法

我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。

当前回答

伪代码基于@biziclop的答案:

只使用基本结构:变量、数组、if、while和for 函数getNode(id)和getChildren(id) 假设已知节点数N

注意:我从1开始使用数组索引，而不是0。

广度优先

S = Array(N)
S[1] = 1; // root id
cur = 1;
last = 1
while cur <= last
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        S[ last+i ] = children[i]
    end
    last = last+n
    cur = cur+1

    visit(node)
end

深度优先

S = Array(N)
S[1] = 1; // root id
cur = 1;
while cur > 0
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        // assuming children are given left-to-right
        S[ cur+i-1 ] = children[ n-i+1 ] 

        // otherwise
        // S[ cur+i-1 ] = children[i] 
    end
    cur = cur+n-1

    visit(node)
end

2018-07-01 14:27:12

其他回答

使用堆栈来跟踪节点

Stack<Node> s;

s.prepend(tree.head);

while(!s.empty) {
    Node n = s.poll_front // gets first node

    // do something with q?

    for each child of n: s.prepend(child)

}

2011-03-11 21:34:29

PreOrderTraversal is same as DFS in binary tree. You can do the same recursion 
taking care of Stack as below.

    public void IterativePreOrder(Tree root)
            {
                if (root == null)
                    return;
                Stack s<Tree> = new Stack<Tree>();
                s.Push(root);
                while (s.Count != 0)
                {
                    Tree b = s.Pop();
                    Console.Write(b.Data + " ");
                    if (b.Right != null)
                        s.Push(b.Right);
                    if (b.Left != null)
                        s.Push(b.Left);

                }
            }

一般的逻辑是，将一个节点(从根开始)推入Stack, Pop()它和Print()值。然后，如果它有子节点(左和右)，将它们推入堆栈-先推右，这样你就会先访问左子节点(在访问节点本身之后)。当stack为空()时，您将访问Pre-Order中的所有节点。

2013-08-09 05:02:24

http://www.youtube.com/watch?v=zLZhSSXAwxI

刚刚看了这个视频，并提出了实施方案。这对我来说似乎很容易理解。请评论一下。

visited_node={root}
stack.push(root)
while(!stack.empty){
  unvisited_node = get_unvisited_adj_nodes(stack.top());
  If (unvisited_node!=null){
     stack.push(unvisited_node);  
     visited_node+=unvisited_node;
  }
  else
     stack.pop()
}

2013-06-28 02:18:34

你可以使用堆栈。我用邻接矩阵实现了图:

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

2013-08-17 12:42:23