计算DFS算法的时间复杂度
Calculating time complexity of DFS algorithm
我接到了一项任务，我必须检查一组人是否有 "close friendship"。这被定义为一群人，其中该组中的所有人都是该组中所有其他人的朋友。到目前为止，我的算法是这样的：
1) 将顶点初始化为未访问
2) 从任意顶点v开始对图进行DFS遍历，将已访问的顶点标记为已访问
3) 如果DFS遍历访问所有顶点，return true
4) 如果不是，return false。
现在我要计算时间复杂度了。但是，总的来说，我在时间复杂度方面遇到了困难，而且我不完全确定该怎么做。我看到它的方式是我遍历我的集合中的所有顶点，这将是...... O（v）？这个对吗？如果是，我该怎么办？
由于在 DFS 中您只访问所有顶点一次，但您遍历每条边以查看该边是将您带到新顶点还是已经看到的顶点，因此 DFS 复杂性的非常准确的度量是 O (#edges).
但是对于 DFS 问题的复杂性，O(#vertices) 通常也是一个可以接受的答案，因为当您看到边没有将您带到新的顶点时，您就不会进一步探索它。
所以当被问到时，你可以给出任何一个答案并解释原因，因为他们都没有错误的支持解释。
但这可能不是您要解决的实际问题的答案。您正试图找到一个联系紧密的小组。
在图形术语中，一组紧密相连的朋友将是其中每个朋友节点与其他所有朋友节点共享一条边的一组朋友。 （重新阅读你的问题 - 它实际上是这样说的。）
在下图中，图的大部分是连通的，并且可以使用 DFTraversal 从一个节点访问其他节点。但是close cohorts是颜色相同的节点组。
我接到了一项任务，我必须检查一组人是否有 "close friendship"。这被定义为一群人，其中该组中的所有人都是该组中所有其他人的朋友。到目前为止，我的算法是这样的：
1) 将顶点初始化为未访问
2) 从任意顶点v开始对图进行DFS遍历，将已访问的顶点标记为已访问
3) 如果DFS遍历访问所有顶点，return true
4) 如果不是，return false。
现在我要计算时间复杂度了。但是，总的来说，我在时间复杂度方面遇到了困难，而且我不完全确定该怎么做。我看到它的方式是我遍历我的集合中的所有顶点，这将是...... O（v）？这个对吗？如果是，我该怎么办？
由于在 DFS 中您只访问所有顶点一次，但您遍历每条边以查看该边是将您带到新顶点还是已经看到的顶点，因此 DFS 复杂性的非常准确的度量是 O (#edges).
但是对于 DFS 问题的复杂性，O(#vertices) 通常也是一个可以接受的答案，因为当您看到边没有将您带到新的顶点时，您就不会进一步探索它。
所以当被问到时，你可以给出任何一个答案并解释原因，因为他们都没有错误的支持解释。
但这可能不是您要解决的实际问题的答案。您正试图找到一个联系紧密的小组。
在图形术语中，一组紧密相连的朋友将是其中每个朋友节点与其他所有朋友节点共享一条边的一组朋友。 （重新阅读你的问题 - 它实际上是这样说的。）
在下图中，图的大部分是连通的，并且可以使用 DFTraversal 从一个节点访问其他节点。但是close cohorts是颜色相同的节点组。