无向图的A*算法

Question

我知道A*算法可以用在有向图中，我们也可以用在无向图中吗？

Answer 1

A* 算法对所有图形都是通用的。所以，是，您可以将它与无向图一起使用。

在 undirected graph 中，根据定义，所有边都是双向的。所以它就像一个方向图，对于每条边，你都会有一个相反方向的边。因此，如果您有一个适用于有向图的算法的实现，您应该能够根据这个原则将它扩展到无向图。

这里唯一的困难是要有合适的数据结构。如果用矩阵实现边缘，你只需要确保 matrix is symmetric。如果使用邻接表，请确保每次添加从 a 到 b 的边时，都会添加 b 到 a 的边，且成本因子相同。