广度优先与深度优先

遍历树/图时,广度优先和深度之间的区别首先是什么？任何编码或伪代码示例都会很棒.

1> dmckee..：

---

这两个术语区分了两种不同的树木行走方式.

展示差异可能是最简单的.考虑树:

    A
   / \
  B   C
 /   / \
D   E   F

一个深度优先遍历将访问节点顺序

A, B, D, C, E, F

请注意,在继续前行之前,你要一条腿向下走.

一个广度优先遍历将访问节点顺序

A, B, C, D, E, F

在这里,我们在下降之前一直在每个级别上工作.

(请注意,遍历顺序存在一些模糊性,我在树的每个级别都保持"阅读"顺序.在任何一种情况下,我都可以在C之前或之后到达B,同样我可以到达E在F之前或之后.这可能或不重要,取决于您的申请......)

---

使用伪代码可以实现两种遍历:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

两个遍历顺序之间的区别在于选择Container.

对于深度优先使用的叠层.(递归实现使用调用堆栈......)

对于广度优先使用队列.

---

递归实现看起来像

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

当您到达没有子节点的节点时,递归结束,因此保证以有限的非循环图结束.

---

在这一点上,我还是有点作弊.随着一点点的小聪明,你也可以工作在这个秩序中的节点:

D, B, E, F, C, A

这是深度优先的变化,我不会在每个节点上做工作,直到我走回树上.然而,我在下来的路上访问了更高的节点以找到他们的孩子.

这种遍历在递归实现中是相当自然的(使用上面的"备用时间"行而不是第一个"工作"行),如果使用显式堆栈则不太难,但我会将其作为练习.

---

值得注意的是,您可以修改深度优先版本以获得前缀(`A,B,D,C,E,F` - 第一个呈现),中缀(`D,B,A,E,C, F` - 用于排序:添加为AVL树,然后读取中缀)或后缀("D,B,E,F,C,A",替代呈现)遍历.名称由您处理根的位置给出.应该注意的是,中缀只对二叉树有意义.@batbrat这些都是名字......考虑到你问过的时间,你可能已经知道了.

2> Yogesh Umesh..：

---

理解条款:

这张图片应该让您了解使用广度和深度这个词的上下文.

---

深度优先搜索:

深度优先搜索算法就好像它想要尽可能快地远离起点.

它通常使用a Stack来记住它到达死胡同时应该去的地方.

要遵循的规则:将第一个顶点A推到 Stack

如果可能,请访问相邻的未访问顶点,将其标记为已访问,并将其推入堆栈.

如果你不能遵循规则1,那么,如果可能的话,从堆栈中弹出一个顶点.

如果您不能遵守规则1或规则2,那么您就完成了.

Java代码:

public void searchDepthFirst() {
    // Begin at vertex 0 (A)
    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;
}

应用程序:深度优先搜索通常用于模拟游戏(以及现实世界中类似游戏的情况).在典型的游戏中,您可以选择几种可能的操作之一.每种选择都会导致进一步的选择,每种选择都会导致进一步的选择,等等,形成一种不断扩展的树形图形.

---

广度优先搜索:

广度优先搜索算法喜欢尽可能接近起点.

这种搜索通常使用a来实现Queue.

要遵循的规则:将顶点A作为当前顶点

访问与当前顶点相邻的下一个未访问的顶点(如果有的顶点),标记它,并将其插入队列.

如果由于没有更多未访问的顶点而无法执行规则1,请从队列中删除顶点(如果可能)并使其成为当前顶点.

如果你因为队列是空的而无法执行规则2,那么你就完成了.

Java代码:

public void searchBreadthFirst() {
    vertexList[0].wasVisited = true;
    displayVertex(0);
    queue.insert(0);
    int v2;
    while (!queue.isEmpty()) {
        int v1 = queue.remove();
        // Until it has no unvisited neighbors, get one
        while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
            vertexList[v2].wasVisited = true;
            // Do something
            queue.insert(v2);
        }
    }
    // Queue is empty, so we're done, reset flags
    for (int j = 0; j < nVerts; j++) 
        vertexList[j].wasVisited = false;
}

应用程序:广度优先搜索首先查找距离起点一个边缘的所有顶点,然后查找距离两个边缘的所有顶点,依此类推.如果您试图找到从起始顶点到给定顶点的最短路径,这将非常有用.

希望这应该足以理解广度优先和深度优先搜索.为了进一步阅读,我将推荐Robert Lafore出色的数据结构书中的Graphs章节.

---

如果我还有十个投票权,我会这样做.