找到一次只訪問一個有向圖的所有頂點的路徑

給定一個有向圖，訪問圖的每個頂點的算法只有一次。這與哈密爾頓循環不同，因爲我不需要在同一個頂點開始和結束的路徑。找到一次只訪問一個有向圖的所有頂點的路徑

回溯算法 想到的一種算法，是回溯，實現並採用遞歸，在此，每一個步驟，您探索所有可能的連接/路徑，並保持一個布爾訪問陣列，以確保沒有頂點訪問不止一次。當向後追溯時，這個布爾值將被設置爲false（回溯中的基本步驟）。基本情況是比較訪問頂點的數量，並查看它與圖中的節點數相匹配，在這種情況下，它將返回true。另一個基本情況是返回false，如果所有頂點都沒有被訪問，但沒有其他連接存在以繼續遞歸。

然而，這樣的時間複雜度將是O(n!)，這是不可取的。

有沒有更好的算法來找到有向圖的路徑/遍歷，它只覆蓋一次圖中的每個頂點。

來源

2017-06-11 saltmangotree

不確定這是否正常工作，但查看強連通的組件（https://en.wikipedia.org/wiki/Strongly_connected_component），並且該圖的縮合可能有助於減少運行時間。但我的感覺是，在最壞的情況下你不會比O（n！）好。 – Henry

如果你有一個有效的算法來解決這個問題，你也可以有效地求解哈密爾頓循環（其中「有效」意思是「在多項式時間內」）：對於任何給定的哈密爾頓循環實例，通過刪除一個頂點。使用高效的算法n次（每個實例一次）在其中找到一個HP（如果存在）。如果在這n個圖中的任何一箇中都有一個HP，並且可以通過添加該圖中刪除的特定頂點將其轉換爲HC，那麼您已經找到了一個HC - 如果沒有，就可以「沒有任何HC。 –

@Henry，據我所知，強連通的組件是那些組件中的每個頂點都可以從同一個組件的另一個頂點到達的組件。雖然有像Tarjan這樣的高效算法，但我覺得我的問題有點不同。我正在尋找只到達所有頂點。你仍然認爲有一個比n更好的解決方案！解決這個問題？ – saltmangotree

根據書算法簡介這個問題是NP完全的。這個問題沒有多項式算法，但沒有證明它不存在。所以在最壞的情況下，你會得到指數級的時間複雜度。

一些筆記。如果圖有一個葉子，那麼這個葉子是路徑的開始或結束。如果圖形有兩個葉子，那麼路徑必須從其中一個開始並以另一個結束。如果圖有三個或更多的葉子，那麼哈密頓路徑不存在。但對於一般圖，沒有快速算法。

來源

2017-06-11 13:33:34

謝謝你。當你說，「所以在最壞的情況下，你會得到指數級的時間複雜度。」，你的意思是n！或者是否有更好的算法是x^y，這比n更好！ – saltmangotree

對不起，我沒有指定它。我的意思是n！ –

找到一次只訪問一個有向圖的所有頂點的路徑

回答

相關問題