algorithm - 检查紧密连接的组件时 DFS 的运行时间

Question

考虑一组 k 人。我想检查组中的每个人是否都是组中所有其他人的 friend 。

为了检查是否所有人都是彼此的 friend ，我会对每个人运行 DFS，检查他们是否与 k-1 个人是 friend 。如果是这样，可以断定他们都是彼此的 friend 。

DFS 的运行时间为 O(V+E)。如果对每个人做一个DFS，运行时间还是O(V+E)吗？

Answer 1

A DFS has the running time O(V+E). Is the running time still O(V+E), if I do a DFS for each person?

不，因为你正在执行搜索 V 次你会有 O(V * (V+E))

虽然这不是您想要的，但您可以使用完整图的属性在 O(V) 中完成此操作，即)如果每个节点的度数为 V，则图是完整的-1。请注意，图表也必须很简单，但它应该适合您的情况