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


当前回答

使用Stack,以下是要遵循的步骤:

如果可能,访问一个相邻的未访问顶点,标记它, 然后把它推到堆栈上。 如果您不能遵循第1步,那么,如果可能的话,弹出一个顶点 堆栈。 如果你不能遵循第1步或第2步,你就完了。


下面是执行上述步骤的Java程序:

public void searchDepthFirst() {
    // begin at vertex 0
    vertexList[0].wasVisited = true;
    displayVertex(0);
    stack.push(0);
    while (!stack.isEmpty()) {
        int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
        // if no such vertex
        if (adjacentVertex == -1) {
            stack.pop();
        } else {
            vertexList[adjacentVertex].wasVisited = true;
            // Do something
            stack.push(adjacentVertex);
        }
    }
    // stack is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++)
            vertexList[j].wasVisited = false;
}

其他回答

使用ES6生成器的非递归DFS

class Node {
  constructor(name, childNodes) {
    this.name = name;
    this.childNodes = childNodes;
    this.visited = false;
  }
}

function *dfs(s) {
  let stack = [];
  stack.push(s);
  stackLoop: while (stack.length) {
    let u = stack[stack.length - 1]; // peek
    if (!u.visited) {
      u.visited = true; // grey - visited
      yield u;
    }

    for (let v of u.childNodes) {
      if (!v.visited) {
        stack.push(v);
        continue stackLoop;
      }
    }

    stack.pop(); // black - all reachable descendants were processed 
  }    
}

它与典型的非递归DFS不同,可以很容易地检测给定节点的所有可达后代何时被处理,并维护列表/堆栈中的当前路径。

如果你有指向父节点的指针,你可以在没有额外内存的情况下完成。

def dfs(root):
    node = root
    while True:
        visit(node)
        if node.first_child:
            node = node.first_child      # walk down
        else:
            while not node.next_sibling:
                if node is root:
                    return
                node = node.parent       # walk up ...
            node = node.next_sibling     # ... and right

注意,如果子节点存储为数组而不是通过兄弟指针,那么下一个兄弟节点可以通过以下方式找到:

def next_sibling(node):
    try:
        i =    node.parent.child_nodes.index(node)
        return node.parent.child_nodes[i+1]
    except (IndexError, AttributeError):
        return None
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中的所有节点。

你可以使用一个堆栈来保存尚未访问的节点:

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile

DFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

BFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.append( currentnode.children );
  //do something
}

两者的对称相当酷。

更新:如前所述,take_first()删除并返回列表中的第一个元素。