邻接表的效率顺序是什么

Question

是O(n+m)还是O(nm)？构建它是 O(nm)，如果我们想搜索、添加或删除一个值，它将是 O(n+m)，对吗？还有什么需要考虑的重要事项吗？

另外，将矩阵转换为列表需要 O(n²)，而将列表转换为矩阵仅 O(nm) 正确？

Answer 1

我认为当您将列表转换为矩阵时：

for each vertex `O(n)`
    for each neighbour `O(n)`

这就是为什么它也是 O(n^2)。

如果 m>n，一个顶点不能拥有所有 m 个邻居，这就是为什么要避免 O(n^3)

例子：

a: b, c, d

b: a, c, d

c: a, b, d

d: a, b, c

完整图表：O(n^2) 列表大小。虽然 n = 4 且 m = 6，但大小是 4x4 而不是 4x6。

(m = (4 * (4-1))/2 = 6 = O(n^2) --全图公式)

Answer 2

构建邻接表的 cost 是从零开始的 O(m)（因为我们可以在 O(1) 中添加任何边）和从邻接矩阵开始的 O(n²)（因为我们必须检查矩阵的每个单元格）。
添加边 u-v 是 O(1)，因为我们可以将条目 v 附加到顶点 u 的邻接列表的末尾
删除一条边 u-v 需要 O(n) 次操作，因为我们必须扫描顶点 u 的邻接列表以便在我们删除它之前找到 v 的条目。
查找是否存在边 u-v 也需要 O(n) 步，因为我们必须扫描顶点 u 的邻接列表并检查是否存在 v 的条目

Remotion and search can me improve to O(logN) or average O(1) using a BST or hashing instead a linked list to store the adjacencies,但是most图算法要求我们扫描一个顶点的整个邻接表而不是检查单个条目，因此我们通常可以很好地使用链表。

我们可以在 O(m) 中将邻接表转换为邻接矩阵，假设矩阵最初用零填充。我们所要做的就是扫描每个顶点的邻接表，对于权重为 W 的每个边 U-V，我们可以做 matrix[U][V] = W（或者 matrix[U][V] = 1，如果图不是加权）。由于我们只查看每条边一次（如果图没有方向，则查看两次），复杂度 os O(m).

邻接表的效率顺序是什么

What is the order of efficiency of an Adjacency list

algorithm

graph-algorithm