algorithm - 为什么 BFS 用 2 种颜色标记节点，而 DFS 用 3 种颜色标记节点？

Question

我突然想到了。

为什么我们在 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

DFS:

  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**

为什么 2 种颜色对 DFS 不够用？为什么 3 种颜色对 BFS 来说是冗余的？

这是另一个 BFS(这次是 3 种颜色):

Answer 1

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

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

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

希望这对您有所帮助!