有向加权图的邻接矩阵与邻接表 [英] Adjacency matrix vs adjacency list for directed weighted graph

问题描述

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

As an exercise I have to build a satnav system which plans the shortest and fastest routes from location to location. It has to be as fast as I can possibly make it without using too much memory.

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

I am having trouble deciding which structure to use to represent the graph. I understand that a matrix is better for dense graphs and that a list would be better for sparse graphs. I'm leaning more towards using a list as I'm assuming that adding vertexes will be the most taxing part of this program.

我只是想听听你们的意见.如果我将典型的路线图视为一个图表，其中各个位置是节点，道路是边缘.你认为它是稀疏的还是密集的?在这种情况下，哪种结构看起来更好?

I just want get some of your guys' opinions. If I were to look at a typical road-map as a graph with various locations being nodes and the roads being edges. Would you consider it to be sparse or dense? Which structure seems better in this scenario?

推荐答案

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

I would go for lists because its only 1 time investment. The good thing about it is that it is able to iterate over all the adjacent vertices faster than matrix which is an important and most frequent steps in most of the shortest path algorithms.

因此，矩阵为 O(N) 的邻接列表仅变为 O(k)，其中 k 是相邻顶点的数量.

So where matrix is O(N) adjacency list goes only O(k) where k is number of adjacent vertices.

这篇关于有向加权图的邻接矩阵与邻接表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！