如何在线性时间内反转图形?

问题描述 投票:9回答:3

我知道有两种表示图形的方法:一种是使用矩阵,另一种是使用列表。

如果我使用矩阵,我必须翻转矩阵中的所有位。这不是需要O(V ^ 2)时间吗?

如果我使用列表,我不是必须逐个遍历每个列表,并创建一个新集合吗?这似乎需要O(V + E)时间是线性的。我对么?

所以,我在这里有另一个问题。例如,考虑我在我的图形上使用Dijkstra算法(矩阵或列表),并且我们使用优先级队列作为场景后面的数据结构。图表表示与数据结构的使用有关系吗?它会影响算法的性能吗?

假设我使用Dijkstra算法的表示和优先级队列列表,Dijkstra的矩阵和使用优先级队列之间会有区别吗?

我猜它只与makeQueue操作有关?或者他们没有什么不同?

algorithm data-structures graph dijkstra
3个回答
© www.soinside.com 2019 - 2024. All rights reserved.