我能否在O(n log*(n))内检测到n条边的无向图中的一个循环?(log*(n)是log*函数)

Question

我有以下算法来检测具有n条边的集合E的无向图中的循环:

for each unvisited edge (u, v) in E:
{
if(Find(u) = Find(v)) // u and v belong to the same set already
{
print "Cycle Detected";
break;
}
else
{
Union(u, v); // put u and v in the same set
}
}

我的问题是我可以实现通过大小和路径压缩方法的联合查找，然后声称代码的时间复杂度为O(n log^*(n))最糟糕的情况呢?

Answer 1

假设你有一个连通图，在最坏的情况下，这个算法将在O(n log*(n))时间内运行。(事实上，它甚至可以在O(n α(n))中运行，其中α(n)是Ackermann函数的增长极其缓慢的逆函数。)但是，如果边的数量非常少，这通常就不成立了。例如，考虑一个有n^2个顶点和n条边的图:即使初始化联合查找数据结构也需要O(n^2)时间。如果这种情况对您很重要，您可以使用坐标压缩或使用哈希表实现联合查找结构，这样您只需处理至少一条边中存在的顶点。对于任何图形，这将在O(n α(n))内运行。