作为练习,我必须构建一个卫星导航系统,该系统可以规划从一个位置到另一个位置的最短和最快的路线。它必须在不使用太多内存的情况下尽可能快。
我无法决定使用哪种结构来表示图形。我知道矩阵更适合密集图,列表更适合稀疏图。我更倾向于使用列表,因为我假设添加顶点将是该程序中最费力的部分。
我只是想听听你们的一些意见。如果我将典型的路线图视为一个图形,其中不同的位置是节点,道路是边缘。你认为它是稀疏的还是密集的?在这种情况下,哪种结构似乎更好?
最佳答案
我会选择列表,因为它只是 1 次投资。它的好处是它能够比矩阵更快地遍历所有相邻顶点,矩阵是大多数最短路径算法中重要且最频繁的步骤。
所以当矩阵是 O(N) 时,邻接列表只需要 O(k),其中 k 是相邻顶点的数量。
关于algorithm - 有向加权图的邻接矩阵与邻接表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36725723/