非递归深度优先搜索算法

Question

我正在寻找一种非递归深度优先搜索算法，用于非二叉树。非常感谢任何帮助。

- mousey

---

@Bart Kiers 一棵树，基于标签来判断。 - biziclop

深度优先搜索是一种递归算法。下面的答案会递归地探索节点，但它们不使用系统调用栈来进行递归，而是使用显式栈。 - Null Set

不，这只是一个循环。根据您的定义，每个计算机程序都是递归的（从某种意义上来说确实如此）。 - biziclop

@Null Set：树也是一种递归数据结构。 - Gumbo

迭代法相较于递归法的主要好处在于，它可以避免大多数系统/编程语言实施的最大堆栈大小/递归深度限制以保护堆栈。使用内存堆栈，您的堆栈仅受程序允许消耗的内存量的限制，通常允许使用比最大调用堆栈大小更大得多的堆栈。 - John B

Answer 1

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()会删除并返回列表中的第一个元素。

- biziclop

---

注意到两种非递归实现方式的相似之处加1（即使它们在递归时有很大的不同，但是在非递归实现时它们仍然很相似...）。 - corsiKa

为了保持对称性，如果你使用一个最小优先队列作为边缘而不是堆栈，则可以得到单源最短路径查找器。 - Mark Peters

顺便提一下，.first() 函数还会从列表中移除元素。就像许多语言中的 shift() 一样。pop() 也可以使用，并且返回的子节点顺序是从右到左而不是从左到右。 - Ariel

根据我的理解，DFS算法存在一些小错误。设想有3个顶点全部互相连接。遍历的顺序应该是：灰(第1个)->灰(第2个)->灰(第3个)->标黑(第3个)->标黑(第2个)->标黑(第1个)。但是你的代码却得出了：灰(第1个)->灰(第2个)->灰(第3个)->标黑(第2个)->标黑(第3个)->标黑(第1个)。 - batman

我可能误解了你的例子，但如果它们都相互连接，那么这并不是一棵树。 - biziclop

Answer 2

您可以使用一个堆栈（stack），其中包含尚未访问的节点：

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

- Gumbo

---

我在想，如果这是一个有环图的话，这个方法还能行吗？我认为我可以避免将重复的节点添加到堆栈中，这样它就能起作用。我的做法是标记弹出的节点的所有邻居，并添加一个if (未被标记的节点)来判断是否适合将其推入堆栈。这样可行吗？ - Alston

@ Stallman，您可以记住已经访问过的节点。如果您只访问尚未访问过的节点，则不会进行任何循环。 - Gumbo

@Gumbo 你所说的“doing cycles”是什么意思？我认为我只想要DFS的顺序。这样对吗？谢谢。 - Alston

只是想指出，使用堆栈（LIFO）意味着深度优先遍历。如果您想使用广度优先，请改用队列（FIFO）。 - Per Lundberg

值得注意的是，要想获得与最受欢迎的@biziclop答案等效的代码，您需要按相反的顺序推送子注释（for each node.childNodes.reverse() do stack.push(stack) endfor）。这也可能是您想要的。为什么会这样的好解释在这个视频中：https://www.youtube.com/watch?v=cZPXfl_tUkA。 - Mariusz Pawelski

Answer 3

如果您有指向父节点的指针，则可以在不使用额外内存的情况下完成此操作。

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

- aaz

---

这是一个很好的解决方案，因为它不使用额外的内存或列表或堆栈的操作（避免递归的一些好理由）。然而，只有当树节点具有指向其父节点的链接时才可能实现。 - joeytwiddle

谢谢。这个算法很棒。但是在这个版本中，你不能在visit函数中删除节点的内存。这个算法可以通过使用“first_child”指针将树转换为单链表。然后你可以遍历它并且不使用递归释放节点的内存。 - puchu

如果你有父节点的指针，就可以不使用额外的内存来完成此操作。但是，存储父节点的指针确实会使用一些“额外的内存”。 - Puttaraju

@rptr87 如果不清楚的话，除了那些指针之外，没有额外的内存。 - Abhinav Gauniyal

这对于不是绝对根节点的部分树会失败，但可以通过 while not node.next_sibling or node is root: 轻松修复。 - Basel Shishani

Answer 4

使用栈来跟踪您的节点。

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)

}

- corsiKa

---

@Dave O. 不行，因为你将访问节点的子节点推到了已经在前面的所有内容的前面。 - biziclop

我一定误解了 push_back 的语义。 - Dave O.

@Dave，你说得很对。我本来想应该是“将队列的其余部分推后”，而不是“推到队尾”。我会进行相应的编辑。 - corsiKa

如果你正在推向前面，那么它应该是一个堆栈。 - flight

@Timmy 嗯，我不确定当时我在想什么。@quasiverse 我们通常将队列视为FIFO队列。栈被定义为LIFO队列。 - corsiKa

@glowcoder- 你能否改用“栈(Stack)”而不是“队列(Queue)”吗？我差点就要给你点个踩，因为使用队列会得到广度优先搜索(BFS)而不是深度优先搜索(DFS)（尽管你把队列当作栈来使用，所以结果是正确的）。 - templatetypedef

Answer 5

一个基于biziclops优秀答案的ES6实现：

root = {
  text: "root",
  children: [{
    text: "c1",
    children: [{
      text: "c11"
    }, {
      text: "c12"
    }]
  }, {
    text: "c2",
    children: [{
      text: "c21"
    }, {
      text: "c22"
    }]
  }, ]
}

console.log("DFS:")
DFS(root, node => node.children, node => console.log(node.text));

console.log("BFS:")
BFS(root, node => node.children, node => console.log(node.text));

function BFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...nodesToVisit,
      ...(getChildren(currentNode) || []),
    ];
    visit(currentNode);
  }
}

function DFS(root, getChildren, visit) {
  let nodesToVisit = [root];
  while (nodesToVisit.length > 0) {
    const currentNode = nodesToVisit.shift();
    nodesToVisit = [
      ...(getChildren(currentNode) || []),
      ...nodesToVisit,
    ];
    visit(currentNode);
  }
}

- Max Leizerovich

Answer 6

虽然“使用堆栈”可能是刻意设计的面试问题的答案，但实际上，它只是明确地执行递归程序在幕后执行的操作。

递归使用程序内置的堆栈。当您调用函数时，它会将参数推送到堆栈上，并且当函数返回时，它会通过弹出程序堆栈来实现。

- Chris Bennet

---

有一个重要的不同之处在于线程栈的容量受到严格限制，非递归算法则会使用更加可扩展的堆。 - Yam Marcovic

这不仅仅是一个虚构的情况。我曾经在C#和JavaScript中使用过这样的技术，以取得比现有的递归调用等效方法更显著的性能提升。通常情况下，通过使用堆栈来管理递归而不是使用调用堆栈，可以更快速地节省资源。将调用上下文放置到堆栈上需要大量开销，而程序员能够对自定义堆栈进行实际决策则更为有效。 - Jason Jackson

Answer 7

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

                }
            }

一般的逻辑是，将一个节点（从根节点开始）推入栈中，然后 Pop() 弹出并打印值。接着，如果它有子节点（左右孩子），则将它们推入栈中——先推入右子节点，这样你就能先访问左子节点（在访问自身节点之后）。当栈为空时，你已经遍历了所有前序遍历的节点。

- Sanj

Answer 8

非递归深度优先搜索（DFS），使用 ES6 生成器。

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

它不同于典型的非递归深度优先搜索，可以轻松检测给定节点的所有可达后代是否已处理，并在列表/堆栈中维护当前路径。

- Jarek Przygódzki

Answer 9

完整的编程示例代码，不包含堆栈：

import java.util.*;

class Graph {
private List<List<Integer>> adj;

Graph(int numOfVertices) {
    this.adj = new ArrayList<>();
    for (int i = 0; i < numOfVertices; ++i)
        adj.add(i, new ArrayList<>());
}

void addEdge(int v, int w) {
    adj.get(v).add(w); // Add w to v's list.
}

void DFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(nodesToVisitIndex, s);// add the node to the HEAD of the unvisited nodes list.
            }
        }
        System.out.println(nextChild);
    }
}

void BFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(s);// add the node to the END of the unvisited node list.
            }
        }
        System.out.println(nextChild);
    }
}

public static void main(String args[]) {
    Graph g = new Graph(5);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.addEdge(3, 1);
    g.addEdge(3, 4);

    System.out.println("Breadth First Traversal- starting from vertex 2:");
    g.BFS(2);
    System.out.println("Depth First Traversal- starting from vertex 2:");
    g.DFS(2);
}}

输出： 广度优先遍历-从顶点2开始: 2 0 3 1 4 深度优先遍历-从顶点2开始： 2 3 4 1 0

- Assaf Faybish

---

nodesToVisit.contains(s) 在节点数量上线性地消耗时间。另一种选择是使用布尔数组跟踪已经访问过的节点，其访问时间为O（1），并占用额外的O（numOfVertices）空间。 - nspo

Answer 10

假设您想在访问图中的每个节点时执行通知。简单的递归实现是：

void DFSRecursive(Node n, Set<Node> visited) {
  visited.add(n);
  for (Node x : neighbors_of(n)) {  // iterate over all neighbors
    if (!visited.contains(x)) {
      DFSRecursive(x, visited);
    }
  }
  OnVisit(n);  // callback to say node is finally visited, after all its non-visited neighbors
}

好的，现在你想要一个基于栈的实现，因为你的例子不起作用。复杂的图形可能会导致程序的堆栈溢出，因此您需要实现非递归版本。最大的问题是要知道何时发出通知。

下面的伪代码可以工作（使用Java和C ++混合编写以提高可读性）：

void DFS(Node root) {
  Set<Node> visited;
  Set<Node> toNotify;  // nodes we want to notify

  Stack<Node> stack;
  stack.add(root);
  toNotify.add(root);  // we won't pop nodes from this until DFS is done
  while (!stack.empty()) {
    Node current = stack.pop();
    visited.add(current);
    for (Node x : neighbors_of(current)) {
      if (!visited.contains(x)) {
        stack.add(x);
        toNotify.add(x);
      }
    }
  }
  // Now issue notifications. toNotifyStack might contain duplicates (will never
  // happen in a tree but easily happens in a graph)
  Set<Node> notified;
  while (!toNotify.empty()) {
  Node n = toNotify.pop();
  if (!toNotify.contains(n)) {
    OnVisit(n);  // issue callback
    toNotify.add(n);
  }
}

看起来很复杂，但发出通知所需的额外逻辑存在是因为您需要按访问的反向顺序进行通知 - DFS从根开始，但最后通知它，不像BFS那样非常容易实现。

为了好玩，尝试以下图形： 节点为s、t、v和w。 有向边为： s->t，s->v，t->w，v->w和v->t。 运行您自己的DFS实现，节点应该被访问的顺序是： w，t，v，s 一个笨拙的DFS实现可能会首先通知t，这表明存在错误。DFS的递归实现始终最后到达w。

- user3804051