algorithm - グラフ内のパスは接続されていますか

Question

グラフのパスに問題があります。たとえば、次の グラフ
が あり
ます 。

そして今、私は質問に答えたいと思います（たとえば）：頂点1が頂点3に接続されている場合。答えはイエスです-パスがあるため、「1-> 2-> 3.

あなたは私に何をアドバイスしますか？

やり方がわかりません。

Answer 1

これには、あなたの側でいくつかの調査が必要になります。アイデアは、深さ優先または幅優先のようなグラフ トラバーサル アルゴリズムを使用することです。頂点 (例では 1 など) から開始し、ターゲット ノード (例では 3) に到達するか、それ以上のパスが見つからなくなるまでグラフをトラバースし続けます。

Answer 2

開始ノードからの DFS または BFS (バックトラッキングが少なくなるため、DFS をお勧めします)。アルゴリズムがノードを検出せずに完了すると、到達できません。