graph - 知道无向图是否连通的最有效算法

Question

我一直在尝试找到一种算法来搜索图是否已连接。该图是无向的，我只想找到一个解决方案（可以有多个）或者如果没有。我在找一个alg。执行接近线性时间，可能是 O(logN) 或 O(NlogN)。

DFS 能否胜任这项任务，或者对于这个特定问题是否有另一种选择？

Answer 1

这将取决于您如何定义N，如果N是顶点数，输入本身可以是 size O(N^2)，并且您将需要阅读所有内容（除非您对输入有一些特定的顺序，并且可能会改变） .

DFS 在O(|V|+|E|)（节点数 + 边数）中运行，并且可以通过简单地计算您发现的新顶点的数量来判断图是否连接，完成后检查这个数字是否为|V|.