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

-3

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

2012-02-27 IAQ

過去1日か2日にグラフ関連のSchemeに関する質問がスタックオーバーフローになっています。例：http://stackoverflow.com/questions/9426788/depth-first-search-dfs-for-undirected-graphsこれは宿題の質問ですか？ – dyoo

はいそれは他のものですが私の投稿ではありません – IAQ

強い推薦：http：//www.htdp.org/2003-09-26/Book/curriculum-ZH-35.html#node_chap_28 ：//www.htdp.org/2003-09-26/Book/curriculum-ZH-38.html – dyoo

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

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

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

出典

2012-02-27 01:52:31

私が書く必要がある関数は、パスがあるかどうかtrueまたはfalseを返すと仮定しています。また、グラフは is_pathと定義されていますか？ '（3（（1 2）（2 3））1 3）ここで、3は頂点の数であり、（（1 2）（2 3））はエッジである。しかし、頂点の数は任意です。私はDijkstraのアルゴリズムを見ましたが、私はまだ完全に失われています。さらなる助けに感謝します。 – IAQ

Dijkstraのアルゴリズムの本質は、それがグラフのエッジ間で一種の推移的閉包を使用することです。たとえば、最初の反復では、a - > bおよびb - > c、a - > cの場合、基本的にグラフの2つのノード間にパスがあることがわかる、または、エッジ間を行き来する可能性のあるさまざまな方法を試して、可能なパスがないことを確認してください。 bruceはこれを行うSchemeの実装に向けてあなたを指摘しました。 –

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

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

出典

2012-02-27 02:20:50 jacobm

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

答えて

関連する問題