最差情況時間深度優先搜索的複雜度

我知道對於這個特定問題的答案是O（V + E），對於像樹這樣的圖，這是有道理的，因爲每個頂點只被探索一次。最差情況時間深度優先搜索的複雜度

但是讓我們假設圖中有一個循環。

例如，讓我們拿一個帶有四個頂點A-B-C-D的無向圖。
A連接到B和C，B和C連接到D.所以總共有四條邊。 A→B，A→C，B→D，C→D，反之亦然。

讓我們來做DFS（A）。

將第一探索B和B的鄰居d和D的鄰居C.該℃後不會有任何邊緣，以便它會回到d和B，然後A.

則A將遍歷其第二邊緣並試圖探索C，因爲它已經被探索，它不會做任何事情，DFS將結束。

但是在這裏頂點「C」已遍歷兩次，而不是一次。顯然最壞情況下的時間複雜度可以直接與V成正比。

任何想法？

來源

2012-08-03 Dude

我在圖中看不到D→C，所以它應該從D開始追蹤。所以遍歷應該是A-> B-> D，A-> C。 – ffledgling 2012-08-03 20:20:05

@Ayos它是一個無向圖，因爲C-> D在那裏D-> C也在那裏，抱歉不正確的表示 – Dude 2012-08-03 20:27:25

如果你不保持visited設置，您用來避免revisitting已訪問節點，DFS不O(V+E)。事實上，它不是完整的算法 - 因此它可能甚至找不到一條路徑，因爲它會陷入無限循環。

請注意，對於無限圖，如果您正在尋找從s到t的路徑，即使保留了訪問集，也無法保證完成，因爲您可能會陷入無限分支。

如果您有興趣保持DFS的高效空間消耗優勢，同時仍然完整 - 您可以使用iterative deepening DFS，但如果您希望發現整個圖表，而不是簡單地解決問題，而不是一個特定的節點。

編輯：DFS僞代碼與visited設置。

DFS(v,visited): 
    for each u such that (v,u) is an edge: 
     if (u is not in visited): 
      visited.add(u) 
      DFS(u,visited)

這是很容易看到你調用遞歸的一個頂點當且僅當尚未訪問過它，因此，答案確實是線性的頂點和邊數。

來源

2012-08-03 20:15:48 amit

我正在使用訪問集，這就是爲什麼BFS從圖中C退回的原因，因爲兩者其鄰居（A，D）已經被探索/訪問。但是，當程序返回到起始節點時，它會再次檢查這個頂點C，但是由於它已經被訪問，它將被忽略並且循環將結束。所以C被訪問兩次IMO如果可能的話，請繪製這張圖表是相同的波長 – Dude 2012-08-03 20:23:29

@Batman：我添加了一個帶DFS的僞代碼，該代碼維護一個「visited」集並最多訪問每個頂點一次，我希望它事情很清楚。 – amit 2012-08-03 20:26:38

你是對的，它不會再遍歷它，謝謝！ – Dude 2012-08-03 20:32:20

您可以訪問圖形的每個頂點和邊緣恆定的次數，仍然是O（V + E）。另一種看待它的方式是，成本被收取到邊緣而不是頂點。

來源

2012-08-03 20:16:00

您可以更具體一些，或者您可以在問題（A，B，C，D）中顯示的圖表背景中告訴我， – Dude 2012-08-03 20:35:13

最差情況時間深度優先搜索的複雜度

回答

相關問題