algorithm - 長さが 3 で割り切れるパスを見つける

Question

無向グラフ (重みなし) と 2 つの頂点uとvが与えられた場合、 uとvの間の長さが 3 で割り切れるパスを見つけるにはどうすればよいでしょうか?

パスは必ずしも単純なパスである必要はないことに注意してください。

DFS のバリエーションと、パスを格納する (およびバックトラッキング用の) スタックについて考えましたが、単純でないパスを追跡する方法も完全には理解できません。

時間計算量は O(V+E) である必要があるため、BFS または DFS のバリアントである必要があります。

Answer 1

これを行う 1 つの方法は、グラフの修正版を計算し、そのグラフで BFS または DFS を実行することです。

グラフをそれ自体の上に 3 回積み重ねると想像してください。各ノードが 3 回表示されるようになりました。最初のコピーに「mod 0」、2 番目のコピーに「mod 1」、3 番目のコピーに「mod 2」と注釈を付けます。次に、ノード u からノード v へのエッジが常にグラフの次の層のノード u からノード v に向かうように、エッジを変更します。したがって、u から v へのエッジがあった場合、u mod 0 から v mod 1 へ、u mod 1 から v mod 2 へ、u mod 2 から v mod 0 へのエッジが存在します。このグラフを使用して、u mod 0 から任意のノード v mod 0 へのパスを見つけると、長さが 3 の倍数でなければならないパスが必ず存在します。

グラフを 2 回コピーし、エッジを適切に再配線することにより、時間 O(m + n) でこのグラフを明示的に構築できます。そこから、BFS または DFS には O(m + n) の時間がかかります。ただし、これはメモリ Θ(m + n) を使用します。

別の解決策は、実際に新しいグラフを作成せずにこれをシミュレートすることです。BFS を実行し、ノードごとに3 つの距離 (mod 0 の距離、mod 1 の距離、mod 2 の距離) を保存します。キューからノードをデキューするときはいつでも、そのサクセサーをエンキューしますが、次の mod レイヤーにあるものとしてタグ付けします (たとえば、ノードをレベル mod 0 でデキューした場合、そのサクセサーを mod 1 でエンキューするなど)。 mod 0、mod 1、および mod 2 の距離でノードに到達したため、特定の mod レベルでノードを複数回キューに入れるべきではありません。これにも O(m + n) の時間がかかりますが、2 番目のグラフを明示的に構築しないため、O(n) のストレージ スペースしか必要ありません。

お役に立てれば！

Answer 2

不正行為の方法:

A から B への DFS/BFS のみ。長さ L % 3 == 0 の場合、終了します。L % 3 == 1、隣人まで歩いて戻ります。それ以外の場合は、隣人まで歩いて行き、また行きます。

---

それが制約を満たさない場合は、次のようになります。

これは、変更された BFS を使用して行うことができます。検索を行っている間、遭遇したすべてのサイクルをマークしてみてください。長さとともにすべての単純なサイクルを取得できます。

その後、A から B へのパスの長さが L % 3 == 0 の場合、それが見つかりました。

そうでない場合、すべてのサイクルの長さが Lk % 3 == 0 の場合、解決策はありません。

長さ K % 3 != 0 のサイクルがいくつかある場合、最初に A からこのサイクルに移動し、1 回または 2 回サイクルしてから A に戻り、次に B に戻ることができます。この方法で長さ 3 のパスを見つけることが保証されます。

Answer 3

ここに疑似コードがあります。BFSと、単純なカウンターとモジュロ テストを使用します。

1. 私:= 0
2. ノード u をキューに入れる
3. i++、ノードをデキューして調べる
4. 要素 v がこのノードで見つかり、 i mod 3 == 0 の場合、検索を終了して結果を返します。それ以外の場合は、まだ検出されていない後続ノード (直接の子ノード) をキューに入れます。
5. キューが空の場合、グラフ上のすべてのノードが調べられました。検索を終了して「見つかりません」を返します。
6. キューが空でない場合は、手順 2 から繰り返します。

注:キューをスタックに置き換えても同様に機能するはずです。その場合はDFSになります。