爲什麼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？

回答

相關問題