algorithm - 有向加权图的邻接矩阵与邻接表

Question

作为练习，我必须构建一个卫星导航系统，该系统可以规划从一个位置到另一个位置的最短和最快的路线。它必须在不使用太多内存的情况下尽可能快。

我无法决定使用哪种结构来表示图形。我知道矩阵更适合密集图，列表更适合稀疏图。我更倾向于使用列表，因为我假设添加顶点将是该程序中最费力的部分。

我只是想听听你们的一些意见。如果我将典型的路线图视为一个图形，其中不同的位置是节点，道路是边缘。你认为它是稀疏的还是密集的？在这种情况下，哪种结构似乎更好？

Answer 1

我会选择列表，因为它只是 1 次投资。它的好处是它能够比矩阵更快地遍历所有相邻顶点，矩阵是大多数最短路径算法中重要且最频繁的步骤。

所以当矩阵是 O(N) 时，邻接列表只需要 O(k)，其中 k 是相邻顶点的数量。