data-structures - 为什么 insertVertex 需要 O(1) 而 deleteVertex 在这里需要 O(m) 我是否正确？

Question

对于作业问题，我被问到给定一组 n 个节点和 m 个边的问题，其中图形由邻接列表表示，为什么 insertVertex 需要 O(1) 而 deleteVertex 需要 O(m)。

我不完全确定我的答案，但我认为 insertVertex 是 O(1) 因为当你第一次插入时，你添加到数组中的只是一个节点和一组相邻的顶点(意味着你的新节点指向的顶点) )。因此这个时间复杂度是恒定的。然而，当你删除一个节点时，你不仅要删除节点和节点附带的相邻边，还必须遍历剩余的 m 条边以确保删除指向的那些您尝试删除的节点(因为您不能拥有指向任何内容的边。

我是图论的新手，所以我不知道我的思维方式是否正确。

Answer 1

O(m) 的解释是正确的。

如果您根据链表操作来解释操作，您的解释会更好。将节点附加到链表需要 O(1) 时间。删除一个项目需要 O(n) 时间。

a) 为什么 insertVertex 是 O(1)？

插入顶点只是将节点附加到链表 (O(1)) 或 2 如果图是无向的。

b) 为什么 deleteVertex 是 O(m)？

删除顶点意味着:

1) 删除链表 (O(1))

2) 在最坏的情况下，您将不得不从所有链表中删除顶点:O(m)。它是 O(m)，因为所有链表中的节点数为 m，如果图是无向图，则为 2*m。