我正确地理解了为什么在这里insertVertex的时间复杂度是O(1)，而deleteVertex的时间复杂度是O(m)吗？

Question

对于一道作业问题，我被问及一个包含n个节点和m条边的图用邻接表表示时，为什么insertVertex需要O(1)，而deleteVertex需要O(m)。

我不是完全确定我的答案是否正确，但我认为insertVertex的时间复杂度为O(1)，因为当你首次插入时，你所添加到数组中的只有一个节点和一组相邻节点（也就是新节点指向的节点）。因此，这个时间复杂度是常数。然而，当你删除一个节点时，你不仅需要删除该节点和与其相关的相邻边，还需要遍历剩余的m条边，以确保删除指向你要删除的节点的边（因为你不能有一条指向空的边）。

由于我对图论不太熟悉，因此我不确定我的想法是否正确。

- KWJ2104

---

听起来对我来说是很有道理的，但我相信其他人在这里能够更加明确。 - pseudoramble

这取决于它是有向图还是无向图，以及数据结构中每个节点是否具有邻居列表或邻居集合。 - kaya3

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。

- philix

Answer 2

insertVertex的时间复杂度为O(1)，因为你只需要将一个新元素添加到数据结构的末尾。

deleteVertex的时间复杂度为O(m)，因为对于每条边，你都需要检查该边是指向还是指出（如果G是有向的）该顶点。

看起来你已经理解了，读了你的原帖。

- codd