我有一个带边的无向图。每条边都有某些属性，例如点A和点B之间的边之一是
{
travelTime :10hours
travelPath : air
}
在C点和D点之间可以是另一个
{
travelTime :1hours
travelPath : Metro
}
我们得到了这样的图和已知的travelPaths
{air, Metro,Rail, Bus ,Auto,Rickshaw }
向我们提供了一组不固定图形的未使用边缘。它们还具有上述属性，只是它们不属于固定图。现在，在此固定图中添加了来自unUsedEdges的边。我们必须告诉您，只有地铁和铁路类型存在一个周期，其中包括这一新引入的优势。 然后删除新引入的边缘，然后检查unUsedEdges中的另一个边缘。如果有一个循环，我们需要循环边缘。我们需要来自所有unUsedEdges边缘的所有循环。
固定图很大。 unUsedEdges设置也很大。我们可以使用DFS在O（V + E）时间中检测无向图中的周期。重复为所有unUsedEdges进行操作需要花费时间。
有更快的解决方法吗？
由于您只想检测地铁或铁路边缘的周期，因此可以通过先运行仅地铁边缘，然后运行铁路边缘的算法来简化问题。因此，可以在没有不同边缘类别的情况下有效地应用算法，以完全解决整个问题。
可以通过使用disjoint-set data structure的变体来解决简化的问题。我们可以将固定边插入数据结构中，然后查询（不插入）每个新边。这告诉我们是否存在循环，但是如果要恢复循环，则需要扩展数据结构。
在数据结构中维护两个父指针数组：一个对于使用路径压缩的不相交联合数据结构正常，而一个不使用路径压缩。在测试非固定边缘时，我们使用路径压缩数组查询是否存在循环，如果存在，则通过跟踪另一个数组中的两个顶点直到它们到达相同的根节点来恢复它。之所以起作用，是因为未压缩数组中的边都是原始固定图的所有边，并且可以从该边形成一个包括未固定边的循环，以及从其每个顶点到同一根节点的两条路径。
在最坏的情况下，总运行时间为O（（m + n）α（v）+ nv），其中v是顶点的数量，m是固定边缘的数量，n是非固定边缘的数量，并且α是增长非常缓慢的inverse Ackermann function。
nv
项之所以存在，是因为这是最坏情况下的输出大小；最多可能有n个周期，每个周期的长度最多为v。如果大多数不固定边缘不创建循环，和/或相对于v，循环通常较短，则运行时间将明显加快。在这种意义上，算法为output-sensitive。