有向グラフのすべての頂点を1回だけ訪れるパスを見つける。

Question

有向グラフでは、グラフの各頂点を1回だけ訪れるアルゴリズムとは何ですか？これはハミルトニアンサイクルとは異なります。つまり、同じ頂点でパスを開始および終了する必要はありません。

頭に浮かぶバックトラッキングアルゴリズム 1つのアルゴリズム、バックトラックされたが、すべてのステップで、あなたはすべての可能な接続/パスを探索し、ブール訪問した配列を維持し、何の頂点が訪問されていないことを確認するために、再帰を使用して実装一回以上。バックトラックをバックワードすると、このブール値はfalseに設定されます（バックトラッキングの必須ステップ）。基本ケースは、訪問された頂点の数を比較し、それがグラフのノードの数と一致することを確認します。その場合、trueを返します。別の基本的な場合は、すべての頂点が訪問されていない場合でも偽を返すことですが、再帰を続けるための他の接続は存在しません。

しかし、これの時間の複雑さは望ましくないO(n!)です。

有向グラフのパス/トラバーサルを見つけるためのより良いアルゴリズムがあります。これは、グラフの各頂点を一度正確にカバーします。

Answer 1

ブックアルゴリズムの紹介この問題はNP完全です。この問題の多項式アルゴリズムはありませんが、存在しないことは証明されていません。したがって、最悪の場合、指数関数的な複雑さがあります。

注意事項 グラフに1つのリーフがある場合、このリーフはパスの開始または終了です。グラフに2つの葉がある場合、パスは一方のパスで開始し、もう一方のパスで終了する必要があります。 グラフに3つ以上のリーフがある場合、ハミルトニアンパスは存在しません。しかし一般的なグラフでは、素早いアルゴリズムはありません。