具有未使用边的循环检测无向图

Question

我有一个带边的无向图。每条边都具有一定的性质，如A点和B点之间的边之一是

{
travelTime :10hours
travelPath : air
}

在C点和D点之间的另一个可以是

{
travelTime :1hours
travelPath : Metro
} 

我们得到了这样一个图和已知的旅行路径

 {air, Metro,Rail, Bus ,Auto,Rickshaw  }

有快一点的吗？

Answer 1

由于您希望只检测metro边或rail边的循环，我们可以通过先运行metro边，然后运行rail边的算法来简化问题。因此，一个不需要不同边缘类的算法可以简单地适应于整个问题。

简化的问题可以使用不相交集数据结构的变化来解决。我们可以将固定的边插入到数据结构中，然后查询（不插入）每个新边。这告诉我们是否存在循环，但如果要恢复循环，我们需要增强数据结构。

在数据结构中维护两个父指针数组：一个是使用路径压缩的不交并数据结构的正常数组，另一个不使用路径压缩。没有路径压缩的图必须保持父指针树中的每个（有向）边都是原始图的（无向）边的不变性质；这意味着有时需要翻转边的方向，以便为联合操作重新根树。

当测试非固定边时，我们使用路径压缩数组来查询是否存在循环，如果存在，我们通过将另一个数组中的两个顶点跟随到它们在父指针树中的最低公共祖先来恢复循环。这起作用是因为未压缩数组中的边都是来自原始固定图的边，而包含未固定边的循环可以从该边加上从其每个顶点到共同祖先的两条路径形成。

在最坏的情况下，总运行时间为O(ma(v)+v²+nv)，其中v是顶点数，m是固定边数，n是非固定边数，a是非常缓慢增长的逆阿克曼函数。

>

m(v)项是union-find数据结构上O(m)个“find”查询的代价。还有另外一个O(n)个“find”查询被执行，但这些查询的术语主要是NV。

v²term是在未压缩数组中重新根树的成本，最多为O(v)次，在最坏的情况下，每次翻转最多为O(v)条边。

nv项是最坏情况下输出的大小；最多可以有n个周期，且每个周期的长度最多可以为v。如果大多数非固定边沿不产生周期，且/或周期通常相对于v较短，则运行时间将显著加快。在这个意义上，该算法是输出敏感的。