运行 检查紧密连接组件时的 DFS 时间
Running time of DFS when checking for closely connected components
考虑一组 k 个人。我想检查组中的每个人是否都是组中所有其他人的朋友。
为了检查是否所有人都是彼此的朋友，我会对每个人进行 运行 DFS，检查他们是否与 k-1 人成为朋友。如果是这样，可以断定他们都是彼此的朋友。
一个DFS有运行宁时间O(V+E)。如果给每个人做一个DFS，运行ning的时间还是O(V+E)吗？
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，则图是完整的。请注意，图表也必须很简单，但它应该符合您的情况
考虑一组 k 个人。我想检查组中的每个人是否都是组中所有其他人的朋友。
为了检查是否所有人都是彼此的朋友，我会对每个人进行 运行 DFS，检查他们是否与 k-1 人成为朋友。如果是这样，可以断定他们都是彼此的朋友。
一个DFS有运行宁时间O(V+E)。如果给每个人做一个DFS，运行ning的时间还是O(V+E)吗？
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，则图是完整的。请注意，图表也必须很简单，但它应该符合您的情况