时间复杂度/图论

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（米）。它是O（m）导致所有链表中的节点数是m，或者如果图是无向的，则为2 * m。

Answer 2

insertVertex花费O（1），因为您只需添加一个新的元素，你的数据结构的结束。

deleteVertex需要O（m），因为对于每一个边，你必须检查边是否指向或从顶点指向（如果G指向）。

看起来你已经有了这个主意，但是，阅读你的OP。