2 つのグラフ ノード間の固定長パス

Question

グラフ上に 2 つのノードが与えられた場合、指定されたホップ数を要するそれらの間のルートを見つけるアルゴリズムはありますか?どのノードも他のノードに接続できます。

現時点の点は 2D 空間に配置されているため、グラフが最適なアプローチかどうかはわかりません。

Answer 1

ノードがホップの観点からルートを検索しようとしている場合、グラフはおそらく正しいアプローチです。ただし、特に「任意のノードを他のノードに接続できる」に関して、あなたが何をしようとしているのか、そしてどのような制約があるのか​​を理解しているかどうかはわかりません。それは少しオープンエンドのようです。

しかし、それを無視して。いくつかのグラフ表現を使用して:

最初のノードから開始して、そこから深さ優先検索を実行し、(a) 取得したホップが指定した数より大きい場合、または (b) 2 番目のノードに到着した場合に検索を終了するように見えます。これにより、（最大で）そのホップ数で 2 つのノードを接続する最初の（だけではない）パスが決定されます。

指定されたホップと正確に一致する必要がある場合、ホップを超えた場合は検索の分岐を終了し、2 番目のノードにも到達した場合は成功で終了します。

Answer 2

反復深化DFS を試しましたか？

Answer 3

ダムアプローチ：（データ構造はスタックの配列です）。これは基本的に深さNまで幅優先検索（BFS）を実行しますが、ループが許可されている場合（明確ではないが、そうであると想定します）、訪問したノードをそれ以上の検索から除外しません。

1. インデックス0（index = depth）の配列に格納されているスタックの開始ノードをプッシュします

2. 各レベル/インデックス＆quot; l＆quot; 0-N：

   レベル「l」に格納されたスタック上の各ノードについて、すべての隣接ノードを見つけ、レベル「l + 1」に格納されたスタックにプッシュします。

   重要：タスクでループを含むパスの検索が許可されている場合、追加したノードに既にアクセスしたかどうかを確認しないでください。ループが許可されない場合、訪問したノードのハッシュを使用して、ノードを2回追加しないようにします**

3. レベル「N-1」を終了したら停止します。

4. インデックス＆quot; N＆quot;でスタックに追加したばかりのすべてのノードをループします。宛先ノードを見つけます。見つかった場合：成功、そうでない場合、そのようなパスはありません。

「すべてのノードを接続できる」場合は、完全に接続されたグラフを意味している場合、実際にノードを訪問することを含まない数学的な答えが存在します

（ただし、式は長すぎてStackOverflowのテキスト入力フィールドに書き込むことができません）