35

スキエナのアルゴリズムに関する本を参照しています。

Gグラフに aHamiltonian pathが含まれているかどうかをテストする問題はですNP-hard。ここで、ハミルトニアン パスPは、各頂点を 1 回だけ訪れるパスです。ハミルトニアン サイクル問題とは異なり、 G の終了頂点から P の開始頂点までのエッジが存在する必要はありません。

有向非巡回グラフ G ( DAG) が与えられ、O(n + m)それがハミルトン路を含むかどうかをテストする時間アルゴリズムを与えてください。

私のアプローチ、

DFSとを使用する予定ですTopological sorting。しかし、問題を解決するために 2 つの概念をどのように結び付ければよいかわかりませんでした。ソリューションを決定するためにトポロジカル ソートをどのように使用できますか。

助言がありますか？

4

1 に答える 1

58

まず、O(n+m) で DAG をトポロジー的に並べ替えることができます (すべての DAG をトポロジー的に並べ替えることができます)。

これが完了すると、エッジがインデックスの低い頂点から高い頂点に移動することがわかります。これは、連続する頂点間にエッジがある場合に限り、ハミルトニアン パスが存在することを意味します。

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

(これは、ハミルトニアン パスでは「戻る」ことができないにもかかわらず、すべてを訪問する必要があるためです。したがって、唯一の方法は「スキップしない」ことです)

この状態は O(n) で確認できます。

したがって、全体の複雑さは O(m+n) です。

于 2013-04-20T20:31:50.623 に答える