在時間O（| E | + | V |）中查找從有向圖的頂點可到達的所有頂點

Where | E |表示邊的數量，| V |頂點的數量。在時間O（| E | + | V |）中查找從有向圖的頂點可到達的所有頂點

我的想法是在給定頂點上使用深度優先搜索來查找可達到的所有頂點。然而就我的理解而言，僅從一個頂點執行深度優先搜索需要O（1 + out-degree（u））時間，其中u是所討論的頂點。

假設深度優先搜索是答案，爲什麼我必須執行完整的O（| V | + | E |）搜索？

來源

2015-04-19 Jake Browning

只有一個頂點的DFS需要O（| E |）。考慮一個完整的圖表作爲最壞的情況，即DFS將遍歷每個邊緣，即使是單個頂點也是如此。您應該意識到「所有頂點可達」是指直接或間接通過另一個頂點，即傳遞。 – stephan

由於

（1）必須不僅在初始頂點，而且在直接連接到它的所有頂點進行深度優先搜索，並在所有的頂點這些頂點被連接到，並等等。（2）在最壞的情況下，所有的頂點都可以從最初的點到達，這相當於執行完整的DFS。

來源

2015-04-19 16:41:16

在我學習的情況下，DFS是使用遞歸dfsFromVertex（v）函數實現的，該函數聲明瞭時間Ɵ（1 + out-degree（v））。這是否意味着在更壞的情況下Ɵ（1 + out-degree（v））=Ɵ（| V | + | E |）？這部分讓我困惑，因爲out-degree（v）可以是| V |最多。我在猜測，我錯誤地認爲1（1 + out-degree（v））是整個遞歸的時間複雜度，但也許它只是遞歸的一次迭代的運行時間。 –

是，每個頂點的Ɵ（1 + out-degree（v））將總共爲Ɵ（| V | + | E |）。一個非常着名的圖論理論指出，每個圖中所有頂點的所有度的和爲2 | E |。是的，這個Ɵ（1 + out-degree（v））用於每個遞歸步驟，並且每個頂點只有一個遞歸步驟。 –

如果您只執行DFS的一個步驟，那麼它就是O（1 + outdegree（v）），但是，它只會得到在一個步驟中從v到達的頂點，但不是所有的頂點你可能會達到。

想想遞歸，爲了檢索所有可到達的頂點，您應該爲每個到達的頂點執行另一個遞歸的DFS搜索。在最壞的情況下，你將到達所有頂點，因此你將得到每個頂點的O（1 + outdegree（v））的總和，所以你將遍歷圖的所有邊並得到O（| V | + | E |）。

來源

2015-04-28 21:37:57

在時間O（| E | + | V |）中查找從有向圖的頂點可到達的所有頂點

回答

相關問題