無向グラフのアルゴリズム*

Question

私はA*アルゴリズムを有向グラフで使用できることを知っていますが、無向グラフでも同様に使用できますか？

Answer 1

A*アルゴリズムは、すべてのグラフに対して一般的です。したがって、はいの場合、無向グラフで使用できます。

undirected graphでは、すべてのエッジは定義上双方向です。つまり、すべてのエッジに対して反対方向のエッジを持つ方向性グラフのようなものです。結果として、有向グラフで動作するアルゴリズムの実装がある場合は、この原理に従って無向グラフに拡張することができます。

ここでの唯一の問題は、適切なデータ構造を持つことです。行列を使って辺を実装する場合は、matrix is symmetricを確認するだけです。隣接リストを使用する場合は、aからbまでの辺を追加するたびに、同じコスト係数でbからaの辺が追加されるようにしてください。