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

它突然出现在我的脑海里。为什么BFS使用2种颜色标记节点，而使用3种颜色的DFS？

为什么我们只使用2 BFS图表颜色traveral都需要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**

为什么两种颜色不够的DFS？为什么BFS有3种颜色的还原剂？

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

enter image description here

来源

2013-02-03 Elad Benda

你能提供一个关于这方面的参考？ BFS和DFS需要什么样的颜色才能说出两种颜色？ – templatetypedef

维基百科。编辑mt q –

有不同数目的在各两个算法的颜色，因为它们被用于表示根本不同类型的信息。

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

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

希望这会有所帮助！

来源

2013-02-03 19:57:12 templatetypedef

我已经添加了3种颜色的BFS示例。为什么这需要？为什么我们需要分类边缘？ –

@ EladBenda-这一切都取决于应用程序。为什么你必须分类边缘并没有根本的原因，你通常不需要。一些实现可能在BFS中使用三种颜色来区分未访问，已访问但尚未扩展以及已访问和已扩展。我真的认为这不值得担心。它完全取决于你想要对搜索做什么，而不是算法的一些基本特征。 – templatetypedef

如果我们用简单的话来解释这一点，那么在BFS中，一旦我们访问了一个节点，就意味着它的所有邻居都被访问了，我们不需要再次访问这个顶点。但是在DFS中，有一种叫做Backtracking的操作，这意味着我们可能需要再次访问一个已经访问过的节点，并且它的所有邻居都不会一次被访问，因此第三个灰色的灰色确认了这样一个事实：“是！它已经访问，你不需要打印它，但有邻居到这个节点仍然没有访问“

来源

2017-10-26 04:44:13

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

回答

相关问题