algorithm - 计算DFS算法的时间复杂度

Question

我接到了一项任务，我必须检查一群人是否有“亲密的友谊”。这被定义为一群人，其中该组中的所有人都是该组中所有其他人的 friend 。到目前为止，我有这个作为我的算法:

1) 初始化未访问的顶点

2) 从任意顶点 v 开始对图进行 DFS 遍历，将已访问的顶点标记为已访问

3)如果DFS遍历遍历所有顶点，返回true

4) 如果不是，返回false。

现在我必须计算时间复杂度。但是，总的来说，我在时间复杂度方面遇到了困难，而且我不完全确定该怎么做。我看到它的方式是我遍历我的集合中的所有顶点，这将是...... O(v)？它是否正确？如果是，我该怎么做？

Answer 1

由于在 DFS 中你只访问所有顶点一次，但是你遍历每条边以查看该边是将你带到一个新的顶点还是一个已经看到的顶点，DFS 复杂度的一个非常准确的度量是 O(#边缘)。

但是对于 DFS 问题的复杂性，O(#vertices) 通常也是一个可以接受的答案，因为当您看到一条边没有将您带到新的顶点时，您就不会进一步探索它。

所以当被问到时，你可以给出任何一个答案并解释原因，因为他们都没有支持解释的错误。

---

但这可能不是您要解决的实际问题的答案。您正试图找到一个紧密联系的小组。

在图形术语中，一组紧密相连的 friend 将是其中每个 friend 节点与所有其他 friend 节点共享一条边。 (重新阅读您的问题 - 它实际上是这样说的。)

在下图中，图的大部分是连接的，并且可以使用 DFTraversal 从一个节点访问其他节点。但紧密队列是具有相同颜色的节点组。