2

我必须存储一些城市以及其中一些城市之间的距离，然后搜索最短路径。从文件中读取城市和距离。我从做一个矩阵开始，但发现它占用了太多空间（超过两倍），所以我改成了一个列表。每个列表项存储 3 个东西：point1、point2 和它们之间的距离。

所以例如我有这个文件：

雅典 斯德哥尔摩 34
斯德哥尔摩 布拉格 23

当我阅读时，它存储在数组中，如下所示：

          _____0______ ______1______
point1   | Athens     | Stockholm   |
point2   | Stockholm  | Prague      |
distance | 34         | 23          |
          ------------ -------------

然后我有一些疑问..这肯定会节省空间，但是否需要更多时间才能完成？该列表是一个数组，但连接（边）以任意方式放置，这就是为什么我开始认为它可能比使用矩阵需要更多时间。

4

4 回答 4

2

您可能想查看图的邻接列表表示，这是您的第二个想法的修改版本，最适合最短路径问题。这个想法是有一个节点表，其中为每个节点存储来自该节点的传出边列表。这允许您迭代所有离开节点的边缘，时间与离开节点的边缘数量成正比，而不是图中的边缘总数（正如您在上面建议的矩阵和列表版本中所拥有的那样）。出于这个原因，大多数进行图搜索的快速算法都使用邻接表。

希望他的帮助！

于 2011-03-18T19:48:12.443 回答
2

将名称与距离分开。创建一个仅包含城市名称的列表。

          _____0______ ______1______ ______2______ 
city     | Athens     | Stockholm   | Prague      |
          ------------ ------------- -------------

然后分别创建矩阵

     __0__ __1__ __2__ 
 0  | 0   | 34  | 0   |
     ----- ----- -----
 1  | 34  | 0   | 23  |
     ----- ----- -----
 2  | 0   | 23  | 0   |
     ----- ----- -----

如果你想搜索一条从布拉格到雅典的路线，那么你首先要找到布拉格和雅典在列表中的位置......

  • 布拉格：2
  • 雅典：0

然后你在矩阵中搜索你的路径。

  • (2,1,23) -> (1,0,34)

最后，您使用列表翻译到城市

  • （布拉格，斯德哥尔摩，23）->（斯德哥尔摩，雅典，34）
于 2011-03-18T20:09:21.563 回答
1

我认为这里的邻接列表肯定是这里的最佳选择。后来在涉及 D/BFS 或 Dijkstra 等算法时非常有用。

如果您不知道如何保持城镇和距离，只需使用一些结构将它们保持在一起。如果您可以使用编号索引的城镇，您将只使用一个简单的对结构（同样最简单的实现是 n 个 STL 对的向量。

当然，如果您不想使用 STL，您应该尝试使用您想要使用的指针来实现自己的结构列表。

于 2011-03-23T08:15:29.213 回答
0

你的方法看起来很好。

为了放松心情，请记住，当您实际上只需要查找预定义数据的单行/条目时，解析单个列表/数组总是比使用两个（或更多）列表更快且资源更友好。

我倾向于不同意这里的其他一些答案，因为我认为没有必要使事情复杂化。查找几个数据单元并额外需要组合这些数据单元以生成结果数据集（正如一些答案所建议的那样），比对列表进行简单的一次性运行以获取一行数据需要更多的步骤. 对于在多个列表中查找和组合分布式数据单元的函数，您只会冒失去 CPU 周期和内存资源的风险，而您当前使用的数据已被组合为完美结果的集合。

Simpler 说：在速度方面，对您当前拥有的列表/数组进行简单的测试是很难被击败的。

于 2013-06-24T06:04:15.210 回答