查找包含有向圖中特定節點的路徑

我有一個有向圖和該圖的一組節點。我想知道是否存在包含集合U中所有節點的路徑（不一定是簡單路徑）。這樣做的最有效方法是什麼？查找包含有向圖中特定節點的路徑

2012-10-19 Tsahi

[你有什麼試過？]（http://mattgemmell.com/2008/12/08/what-have-you-tried/）你爲什麼認爲你決定實施的方法效率不夠高？ –

尋找「Hamilton Path」或「Hamilton Cycle」。 – krlmlr

「Hamilton路徑」僅適用於無向圖，它必須是一條簡單的路徑。 – Tsahi

提示：如果可以從原始圖G中的e的源頭到達目標，則在E'中用e'創建一個圖G'=（U，E'）。（可達性的確切計算取決於您是否允許節點被訪問兩次。）

現在，你有什麼要檢查G'爲了解決你的問題？

2012-10-19 22:32:26 krlmlr

G'中必須至少有一個節點與其他節點中的每一個都有邊，但是我我不確定它是否能保證路徑的存在。創造G'將花費O（n^2）時間，不是嗎？ – Tsahi

@ user1758674：如果我正確理解您的問題，我認爲這既不夠充分也不必要。構造將需要至少O（E'），在最壞的情況下可能是O（n^2）。 – krlmlr

回答