如何在圖中找到包含一組節點的循環？

給定一個圖無向G =（V，E）和一組節點P.我需要找到一個包含這些節點的週期（不是最短長度週期）？我如何找到這個循環？如何在圖中找到包含一組節點的循環？

來源

2010-10-11 Bruce

你有任何條件在所需的週期？ – Frank 2010-10-11 17:11:30

循環中沒有條件 – Bruce 2010-10-11 17:14:12

您是否在尋找歐拉循環？ – mattbasta 2010-10-11 17:27:38

包含哈密爾頓週期（對於P = V），因此決策問題（只知道是否有這樣的事情）是NP完全的。所以沒有有效的算法，除非P = NP。

來源

2010-10-11 18:46:08 piccolbo

我可能會開始通過選擇P中的第一個節點（我們稱之爲P [0]）來設計算法，然後從P [0]運行深度優先搜索，並記下任何時候P [0]是再次達到。您必須存儲重新達到P [0]的路徑（或者至少是否已到達P的其他節點），以便您知道任何找到的週期都包含P中的所有節點。運行時間應該是與深度優先搜索相同，我相信它是O（V + E）。

有人可能會想出更好的解決方案，並且某些啓發式技術可能會用於幫助，但這應該讓您開始。（例如，你可以得出結論，你應該在P的節點與邊緣，而不是爲P開始[0]最少的開始。）

編輯：我認爲

一件事...當通過深度優先搜索到達P中的另一個節點時，不需要從頭開始「重新開始」，或者考慮不包含這個新找到的節點的路徑。在沒有這種循環的情況下，該屬性可以幫助您更快地終止算法。

進一步編輯：

沒關係最後一次編輯 - 它只會工作，如果它能夠確定有屬於P P [0]和P中的節點之間的不同路徑上沒有節點達不到另一種方式無法達到的程度，而且我們不知道如果沒有整個DFS的話。

關於哈密爾頓週期的答案，我不知道在手邊的問題中的週期檢測是如何完成的。是的，我們必須遍歷從起始點到達的整個圖（所有頂點和邊），以確定是否存在符合問題標準的週期。此外，我們需要知道在與先前訪問的頂點接觸時，頂點的「前進路徑」將確定是否存在滿足標準的循環。因爲我們不關心最短的這種循環，但我不確定我們是如何找到哈密爾頓循環的。照顧開導？

來源

2010-10-11 17:17:52 Andrew

哈密頓循環遍歷所有節點，因此不會更短或更長。讓我一步一步來。考慮這個問題的特殊情況（如果特例是NP-hard，一般情況也是NP-hard）：圖G =（V，E）和節點集P = V（這就是它的特殊之處案件）。現在，通過所有節點V的最短和最長週期同樣長，| V |。問題變得只是發現是否存在這樣的事情，而這正是哈密爾頓週期，它是NP完全的。所以我只是發現HC在這個問題的「內部」。問題不在於HC，而是包含它。說得通？ – piccolbo 2010-10-14 17:59:05

如何在圖中找到包含一組節點的循環？

回答

相關問題