计算DFS算法的时间复杂度

Question

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

1）将顶点初始化为未访问

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

3）如果DFS遍历访问所有顶点，则返回true

4）如果没有，则返回false。

现在我必须计算时间复杂度。但是，我在时间复杂性方面遇到了困难，我并不完全确定如何做到这一点。我看到它的方式是我遍历我的集合中的所有顶点，这将是...... O（v）？它是否正确？如果是的话，我该怎么办呢？

Answer 1

因为在DFS中，您只访问所有顶点一次，但是您在每个边缘移动以查看该边缘是否将您带到新顶点或已经看到的顶点，DFS复杂度的非常准确的度量是O（#edges）。

但是O（#vertices）对于DFS问题的复杂性来说通常也是一个可接受的答案，因为当你看到边缘没有带你到一个新的顶点时，你不会进一步探索它。

所以当被问到时，你可以给出答案并解释推理，因为它们都不支持解释。

---

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

在图形术语中，紧密连接的朋友组将是每个朋友节点与每个其他朋友节点共享边缘的朋友。 （重新阅读你的问题 - 它实际上是字面意思。）

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