广度第一VS深度第一
当遍历树/图时，宽度优先和深度优先之间的区别是什么？ 任何编码或伪码的例子都会很棒。
这两个术语区分了走树的两种不同方式。
只是展现其中的差异可能是最简单的。 考虑树：
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
这是深度优先的变体，在那里我不会在每个节点上完成工作，直到我走回树上。 然而，我已经在下降的路上访问了更高的节点以找到他们的孩子。
这种遍历在递归实现中相当自然（使用上面的“Alternate time”行而不是第一个“Work”行），如果使用显式堆栈，则不会太困难，但我将其作为练习。
了解这些条款：
这张图片应该给你一个关于广度和深度使用的上下文的想法。
深度优先搜索：
深度优先搜索算法就好像它希望尽可能快地远离起点。
它通常使用Stack来记住它到达死胡同时的位置。
遵循的规则：将第一个顶点A推到Stack
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;
}
应用程序：深度优先搜索通常用于模拟游戏（和现实世界中的类似游戏的情况）。 在典型的游戏中，您可以选择几种可能的操作之一。 每一种选择都会导致更多的选择，每种选择都会导致进一步的选择，从而形成一个不断扩大的可能性树形图。
广度优先搜索：
Queue实现。 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章节。
我认为写这两个代码会很有趣，只有通过切换某些代码行才能给出一种算法或另一种代码，以便您会发现dillema的强度并不像看起来那么强大。
我个人喜欢把BFS解释为淹没景观：低海拔地区将首先被洪水淹没，然后才会出现高海拔地区。 如果您将地形高度视为等值线，就像我们在地理书中看到的那样，它很容易看到BFS同时填充同一等值线下的所有区域，就像物理学一样。 因此，将海拔高度解释为距离或比例成本可以给出算法的相当直观的概念。
考虑到这一点，您可以轻松地调整广度优先搜索背后的想法，轻松找到最小生成树，最短路径以及许多其他最小化算法。
我没有看到DFS的任何直观的解释（只有关于迷宫的标准，但它不像BFS和洪水一样强大），所以对我来说，似乎BFS似乎与上述的物理现象更好地相关，而DFS与理性系统（即人们或计算机决定在棋牌游戏中制作哪种动作或走出迷宫）的选择关系更好。
所以，对于我来说，自然现象与现实生活中的传播模型（横向）最匹配的谎言之间的区别。
链接地址: http://www.djcxy.com/p/60215.html