algorithm - 偶数パス アルゴリズム -DFS

Question

まず、私は嘘をつきません。これは私の宿題です。私はこの質問を何時間も解決しようとしていますが、手がかりがありません.

特定の頂点から他のすべての頂点への偶数長のパスを持つすべての頂点を見つけるアルゴリズム (効率的) を作成する必要があります。

おそらくDFSの使用に伴うものだと思います...

どなたかご指南ください！

Answer 1

それは宿題なので、私はいくつかのヒントを提供しているだけです：

1. セットを維持せずに特定の深さまでDFSを実行する場合、visited「検出」するすべての頂点には、現在の深さに等しい長さのソースからのパスがあります。
2. 深さまでDFSを実行する2|V|と、ソースからのパスが偶数のすべての頂点が、深さレベルで検出されます。[理由を確信してください：奇数の長さのサイクルではどうなりますか？偶数のサイクルではどうなりますか？]

注意：実行時間は頂点の数で指数関数的になります[2倍]。

Answer 2

ノードiごとに、3つのブール状態を作成します
（i、0）：未到達
（i、1）：奇数の長さで到達可能
（i、2）：
最初は偶数の長さで到達可能それらはすべてゼロ
であり、次に、 dfsは
、ノードの状態を変更しないことがわかった場合に、アクセスしたノードの状態をdfs内で変更して、このスレッドを停止できます。
変更できる状態は全部で3*nあるので、必要な最大時間は
O（m）で、エッジの数です〜

Answer 3

実行時間について心配ですか？それはもう議論されましたか？セットの効率的なデータ構造について話しましたか？いいえの場合、amitのヒントが役立ちます。

もしそうなら、あなたは多分もっと賢いはずです。DFSについて話し合ったときに、以前にアクセスした頂点のセットを維持することについて話しましたね。

代わりに、複数のセットを維持することができます。各セットは、わずかに異なる意味を持ちます。訪問したセットがこれらの個別のセットの和集合であると想像するかもしれませんが、重要なことに、頂点が1つに表示され、後で別の頂点に表示される場合は、頂点を再表示する必要があります。

自問してみてください：頂点をどのセットに入れることができますか？頂点が訪問によってすでにいくつかのセットに結合されている場合、いつそれを再訪問する必要がありますか？ここでは簡単に間違いを犯す可能性があるので注意してください。