广度第一深度第一
当遍历一棵树/图时，宽度优先和深度优先之间的区别是什么？ 任何编码或伪代码的例子会很好。
这两个术语区分了两种不同的行走方式。
只是展现其中的差异可能是最简单的。 考虑树：
A / \ BC / / \ DEF 深度优先遍历将按此顺序访问节点
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的select。
- 为了深度首先使用一个堆栈。 （recursion实现使用调用堆栈…）
- 广度优先使用队列。
recursion实现看起来像
ProcessNode(Node) Work on the payload Node Foreach child of Node ProcessNode(child) /* Alternate time to work on the payload Node (see below) */
当你到达一个没有子节点的节点时recursion结束，所以它将保证结束有限的非循环图。
在这一点上，我还是骗了一点。 有一点聪明，你也可以按照这个顺序在节点上工作 ：
D, B, E, F, C, A
这是一个深度优先的变化，在那里我不在每个节点上工作，直到我走回树上。 然而，我却在上下路途中访问了更高的节点去寻找他们的孩子。
这个遍历在recursion实现中是相当自然的（使用上面的“Alternate time”行而不是第一个“Work”行），如果使用显式堆栈，也不会太难 ，但是我将把它作为一个练习。
这是一个有点晚的答案，但我想分享一些有用的观点在这个话题上：
了解条款：
这张图片应该给你关于广度和深度使用的上下文的想法。
深度优先search：
-
深度优先的searchalgorithm就好像它想要尽可能快地从起始点离开。
-
它通常使用
Stack来记住它到达死胡同时应该到达的位置。 -
遵循的规则：将第一个顶点A推到
Stack- 如果可能的话，访问邻近的未访问顶点，将其标记为已访问，并将其推入堆栈。
- 如果你不能遵循规则1，那么，如果可能的话，从堆栈中popup一个顶点。
- 如果你不能遵循规则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; } -
应用程序 ：深度优先search通常用于游戏模拟（和真实世界中的类似游戏的情况）。 在典型的游戏中，您可以select几种可能的操作之一。 每个select导致进一步的select，每个select导致进一步的select，等等进入一个不断扩大的树形图的可能性。
广度优先search：
- 广度优先searchalgorithm喜欢尽可能靠近起点。
- 这种search通常使用
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; } -
应用程序 ：广度优先search首先查找离开始点一个边的所有顶点，然后查找两个边相离的所有顶点，依此类推。 如果您正在尝试查找从起始顶点到给定顶点的最短path，这非常有用。
希望这对于理解广度优先search和深度优先search应该足够了。 为了进一步阅读，我将推荐Robert Lafore出色的数据结构书中的Graphs章节。
我认为写这两个代码是很有意思的，只有通过切换一些代码才能给出一个algorithm或另一个代码，这样你就可以看到你的dillema没有看起来那么强大。
我个人喜欢把BFS解释为洪水泛滥：低海拔地区将首先被洪水淹没，只有高海拔地区才会出现。 如果您将地形高度视为等值线，我们可以很容易地看到，BFS同时填充同一个等值线下的所有区域，就像物理学一样。 因此，将高度解释为距离或缩放成本给出了algorithm的相当直观的概念。
考虑到这一点，您可以轻松地调整广度优先search背后的思想，以轻松find最小生成树，最短path以及许多其他最小化algorithm。
我没有看到DFS的任何直观的解释（只有标准的迷宫，但它不像BFS和淹没一样强大），所以对我来说，似乎BFS似乎与上述物理现象更好地相关，而DFS与理性系统（即人们或计算机决定在棋牌游戏中做出的动作或走出迷宫）的select关系更好。
所以，对于我来说，自然现象与现实生活中的传播模型（横向）最匹配的谎言之间的区别。
