java - 表示节点之间路径长度的数据结构？

Question

好吧，我是 Java 新手，我问这个问题是因为我确信有一种更好的简单方法可以解决这个问题，而且那里更有经验的人可能会给我一些建议。

我有一张城市图，它们之间的路径长度。我正在尝试使用 Java 构建一个算法，从起始城市到目的地城市，找到最短路径。每个城市都有一个名称和 map 坐标。更具体地说，我将使用 A* 算法，但这(可能)对我的问题并不重要。

我的问题是我试图找出一种用长度表示节点和它们之间的路径的好方法。

我能想到的最简单的方法是创建一个巨大的二维方形数组，每个城市由一个索引表示，其中连接的城市可以由它们在数组中的相交位置表示。我为每个城市分配了一个索引#。在数组值中，0 会指向没有连接的地方，距离会指向有连接的地方。

我还将有一个带有“索引”属性的城市子类，其索引值在数组中。这样做的缺点是要找出哪些城市有连接，必须有额外的步骤来查找数组中城市的索引是什么，还必须查找哪个连接的城市有连接索引。

有没有更好的方法来表示这一点？

Answer 1

另一种方法是使用一个节点结构来存储指向相邻节点的所有指针。

例如。

如果你的数据结构中有这样的东西

   A   B   C

A  /   0   1

B  0   /   1

C  1   1   /

在新结构中，它将是

A: [C]
B: [C]
C: [AB]

与您的二维数组方法相比，这种方法需要更长的时间来检查两个节点是否连接，但占用的空间更小