無向グラフパスを見つけるアルゴリズム

Question

無向グラフでパスを見つける簡単なアルゴリズムとは何ですか？

Answer 1

この質問に対する回答は、グラフの表現に依存します。典型的なアルゴリズムはDijkstraのアルゴリズムです（このアルゴリズムは最短経路を見つけるが、それはうまくいく）。

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

これは、実装するために、かなり単純なアルゴリズムだし、パスの中でおそらく最も直感的なアルゴリズムを見つけます。

Answer 2

パスが存在するかどうかを調べる最も簡単な方法は、depth-first searchを実装することです。 Schemeで他の種類の再帰的プログラミングを行ったことがあれば、深さ優先検索はかなり自然になるでしょう。アイデアは、各ノードに対して、それが完了した宛先である場合です。それ以外の場合は、それぞれの子に再帰します。

唯一のキャッチは、同じノードを2回訪れるのを避けるために、トラバーサル中にすでに訪れたノードを追跡する必要があることです。そうでなければグラフA < - > B < - > Cがあり、AがCに接続しているかどうかを確認しているなら、無限にAからBへ、次にBからAへ、AからBへ、そうして永遠に。