图中的算法复杂度

Question

我想删除一个使用邻接表的图。删除列表的算法的复杂度为O(N)，其中N是列表中元素的数量，并且工作正常，顶点也是使用链表连接的，我想看看我的删除图的算法是否正确，如果是的话，它的复杂性。

1º If the graph doesn't exist, exit.
2º If there are no vertexes, erase graph, exit.
3º Delete the adjacency list of the first vertex, if it exists.
4º Delete the first vertex.
5º Repeat the function recursively.

提前感谢

Answer 1

乍一看，它看起来是正确的。

我对第五步只有一点点不太确定

5º递归地重复该函数。

从前4步开始，我假设你有一个包含顶点列表的图形对象。然后，逻辑解决方案是遍历每个顶点，删除它的边，然后是顶点本身。

但是，您可以使用“递归”这个词来具体描述步骤5。

所以我假设这意味着对于每个顶点，你首先存储它的邻居，然后删除边，然后节点本身，然后迭代存储的邻居。

现在你检查得太多了。如果你有一个由n个节点组成的完全互连的图，你要检查每个顶点n-1次。不过，这只是你第一次真正工作的时候。所以我不能100%确定这是否仍然算作O(n)。

如果您保留了所有要执行的顶点的列表，并且在检查某个顶点时，仅当其邻居不在该列表中时才将其添加到该列表中。(例如，如果您在java中使用一个Set，则它不能包含双精度)。那就不成问题了。

在每次迭代之后，您只需从待办事项列表中取出下一个顶点，并重复该列表，直到该列表为空。每个连接的顶点将恰好放入该列表中一次。所以总的复杂度是O(n)。