用於在DAG中查找Hamilton路徑的算法

我指的是Skienna的算法書。用於在DAG中查找Hamilton路徑的算法

測試的圖形G是否包含Hamiltonian path問題是NP-hard，其中哈密爾頓路徑P是訪問每個頂點恰好一次的路徑。與漢密爾頓週期問題不同的是，從G的結束頂點到P的起始頂點不必存在邊。給定一個有向無環圖G（DAG），給出一個O(n + m)時間算法來測試它是否包含哈密爾頓路徑。

我的做法，

我打算使用DFS和Topological sorting。但我不知道如何連接這兩個概念來解決問題。如何使用拓撲排序來確定解決方案。

有什麼建議嗎？

來源

2013-04-20 user2302617

您可以先在O（n + m）中對DAG進行拓撲排序（每個DAG可以進行拓撲排序）。

完成此操作後，您知道邊緣從較低索引頂點變爲較高。這意味着當且僅當連續頂點之間存在邊時，才存在哈密爾頓路徑。

(1,2), (2,3), ..., (n-1,n).

（這是因爲在哈密爾頓路徑，你不能「回頭」，但你必須訪問所有，所以唯一的辦法就是「不跳過」）

您可以檢查此條件在O（n）中。

因此，總體複雜度爲O（m + n）。

來源

2013-04-20 20:31:50

@彼得伊凡諾夫謝謝！ – user2302617 2013-04-20 20:41:02

但是您認爲圖形已連接，對於具有斷開連接的零件的圖形，不能有拓撲排序嗎？ – shinzou 2016-03-14 20:55:21

我不假定圖形是連通的。如果圖形沒有連接，那麼就沒有哈密爾頓算子，並且這個算法會檢測到它，因爲至少有一個連續的頂點不會被連接（否則圖形將被連接）。 – 2016-03-18 19:03:02

我不認爲@agassaa的聲明是完全正確的。考慮一個簡單的例子，其中有三個節點「A」，「B」，「C」和邊A-> B，B-> C，A-> C。 A有兩個孩子，C有兩個父母，A-> B-> C構成哈密頓路徑。您不需要遍歷圖中的每條邊，以使路徑成爲哈密爾頓算子。

A DAG that has Hamiltonian cycle

來源

2016-08-02 04:54:37 kakadong

用於在DAG中查找Hamilton路徑的算法

回答

相關問題