遍历树/图时,广度优先和深度之间的区别首先是什么?任何编码或伪代码示例都会很棒。
这两个术语区分了两种不同的树木行走方式。
展示差异可能是最简单的。考虑树:
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
这是深度优先的变化,我不会在每个节点上做工作,直到我走回树上。然而,我在下来的路上访问了更高的节点以找到他们的孩子。
这种遍历在递归实现中是相当自然的(使用上面的“备用时间”行而不是第一个“工作”行),如果使用显式堆栈则不太难,但我会将其作为练习。
这张图片应该让您了解使用广度和深度这个词的上下文。
Stack
记住它到达死胡同时应该去的地方。Stack
上
如果可能,请访问相邻的未访问顶点,将其标记为已访问,并将其推入堆栈。
如果你不能遵循规则1,那么,如果可能的话,从堆栈中弹出一个顶点。
如果您不能遵守规则1或规则2,那么您就完成了。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
来实现。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章节。
鉴于这个二叉树:
广度优先遍历: 从左到右遍历每个级别。
“我是G,我的孩子是D和我,我的孙子是B,E,H和K,他们的孙子是A,C,F”
- Level 1: G
- Level 2: D, I
- Level 3: B, E, H, K
- Level 4: A, C, F
Order Searched: G, D, I, B, E, H, K, A, C, F
深度优先遍历: 遍历不是一次完成整个级别的遍历。相反,遍历首先潜入树的DEPTH(从根到叶)。然而,它比简单的上下都复杂一点。
有三种方法:
1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:
Grab the Root. (G)
Then Check the Left. (It's a tree)
Grab the Root of the Left. (D)
Then Check the Left of D. (It's a tree)
Grab the Root of the Left (B)
Then Check the Left of B. (A)
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)
Check the Right of D. (It's a tree)
Grab the Root. (E)
Check the Left of E. (Nothing)
Check the Right of E. (F, Finish D Tree. Move back to G Tree)
Check the Right of G. (It's a tree)
Grab the Root of I Tree. (I)
Check the Left. (H, it's a leaf.)
Check the Right. (K, it's a leaf. Finish G tree)
DONE: G, D, B, A, C, E, F, I, H, K
2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.
Check the Left of the G Tree. (It's a D Tree)
Check the Left of the D Tree. (It's a B Tree)
Check the Left of the B Tree. (A)
Check the Root of the B Tree (B)
Check the Right of the B Tree (C, finished B Tree!)
Check the Right of the D Tree (It's a E Tree)
Check the Left of the E Tree. (Nothing)
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...
Onwards until...
DONE: A, B, C, D, E, F, G, H, I, K
3) POSTORDER:
LEFT, RIGHT, ROOT
DONE: A, C, B, F, E, D, H, K, I, G
用法(又名,我们为什么关心): 我真的很喜欢这个简单的Quora解释深度优先遍历方法以及它们如何被常用: “按顺序遍历将打印值[为了BST(二叉搜索树)]” “预订遍历用于创建[二叉搜索树]的副本。” “Postorder遍历用于删除[二叉搜索树]。” https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing
我认为以一种方式编写它们会很有意思,只有通过切换一些代码行才会给你一个算法或另一个算法,这样你就会发现你的dillema并不像看起来那么强大。 。
我个人喜欢将BFS解释为淹没景观:低海拔地区将首先被淹没,然后才会出现高海拔地区。如果你把地形书中的景观高度想象为等值线,很容易看出BFS同时填充同一等值线下的所有区域,就像物理学一样。因此,将高度解释为距离或缩放成本可以非常直观地了解算法。
考虑到这一点,您可以轻松地调整广度优先搜索背后的想法,以便轻松找到最小生成树,最短路径以及许多其他最小化算法。
我还没有看到任何关于DFS的直观解释(只有关于迷宫的标准解释,但它不像BFS那样强大并且泛滥),所以对我而言,似乎BFS似乎与如上所述的物理现象更好地相关,而DFS与理性系统上的选择dillema(即人或计算机决定在国际象棋比赛中进行哪些移动或走出迷宫)的关系更好。
所以,对我而言,自然现象与现实生活中的传播模型(横向)最匹配的谎言之间的区别。