我知道有两种表示图形的方法:一种是使用矩阵,另一种是使用列表。
如果我使用矩阵,我必须翻转矩阵中的所有位。这不是需要O(V ^ 2)时间吗?
如果我使用列表,我不是必须逐个遍历每个列表,并创建一个新集合吗?这似乎需要O(V + E)时间是线性的。我对么?
所以,我在这里有另一个问题。例如,考虑我在我的图形上使用Dijkstra算法(矩阵或列表),并且我们使用优先级队列作为场景后面的数据结构。图表表示与数据结构的使用有关系吗?它会影响算法的性能吗?
假设我使用Dijkstra算法的表示和优先级队列列表,Dijkstra的矩阵和使用优先级队列之间会有区别吗?
我猜它只与makeQueue
操作有关?或者他们没有什么不同?