2

它突然出现在我的脑海中。

为什么我们在 BFS 图遍历中只使用 2 种颜色

DFS 需要 3 个吗？

例如：来自维基百科：

BFS：

procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t ← Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
12             u ← G.adjacentVertex(t,e)
13             if u is not marked:
14                  **mark u**
15                  enqueue u onto Q
16     return none

文件系统：

  procedure DFS(G,v):
2      label v **as explored**
3      for all edges e in G.adjacentEdges(v) do
4          if edge e is unexplored then
5              w ← G.adjacentVertex(v,e)
6              if vertex w is unexplored then
7                  label e as a **discovery edge**
8                  recursively call DFS(G,w)
9              else
10                 label e as a **back edge**

为什么 DFS 2 种颜色不够用？为什么 BFS 会减少 3 种颜色？

这是另一个 BFS（这次是 3 种颜色）：

在此处输入图像描述

4

3 回答 3

3

这两种算法都有不同数量的颜色，因为它们用于表示根本不同类型的信息。

在 BFS 和 DFS 中，节点都需要标记为未探索节点或已探索节点。至少需要两种颜色来表示此信息。

在您上面列出的 DFS 实现中，该实现还使用颜色将边缘分类为“发现边缘”（形成算法产生的深度优先搜索树的边缘）或“后边缘”（从更深的边缘移动的边缘） DFS 树的一部分到 DFS 树的较浅部分）。这些颜色用于为边缘着色，而不是节点。因此，边缘需要三种颜色 - 未探索边缘、“发现”边缘和后边缘。

希望这可以帮助！

于 2013-02-03T19:57:12.847 回答
0

在 BFS 的应用中，我们也需要 3 种颜色的节点。一个简单的例子是使用 BFS只打印一次无向图的每个顶点和边。我们不能只用两种颜色来做到这一点。要了解为什么会这样，让我们​​考虑一下位于我们当前正在探索的边的另一端的顶点的状态（用于迭代）。另一端的顶点可以是 (a) 已经处理 (b) 尚未发现 (c) 已经坐在队列中，等待处理。如果是（a），我们之前已经看到了当前边，所以我们不需要再次打印它。对于（b）和（c），我们是第一次看到它，我们需要打印它。好的，足够好了。所以，我们决定只使用一个标志，visitedtruefalse对于 (b) 和 (c)，我们可以决定何时打印边缘，何时不打印。但是，因此，我们刚刚确定我们需要为队列中的顶点保留visited标志，即案例 (c)。false因此，我们将无法在推入队列时对其进行标记。只有当我们探索了与它相连的所有边时，我们才能标记它。结果，当在迭代中遇到情况（c）时，我们将无法判断另一端的顶点是否已经在队列中（除非我们明确搜索队列）。我们最终会再次将其推入队列并最终得到错误的答案。

于 2018-09-26T23:00:42.490 回答
0

如果我们用简单的话来解释这一点，在 BFS 中，一旦我们访问了一个节点，它就意味着它的所有邻居也都被访问了，我们不需要再次访问那个顶点。但是在 DFS 中，有一个称为 Backtracking 的操作，这意味着我们可能需要再次访问一个已经访问过的节点，并且它的所有邻居都不会一次被访问，因此使用第三种颜色灰色表示“是的！它已被访问过”并且您不需要打印它，但是该节点的邻居仍然没有被访问”

于 2017-10-26T04:44:13.320 回答