检测增量图中的循环

Question

鉴于我有一个最初是空的图，它将逐渐添加边缘（一个接一个），那么检测和识别出现的循环的最佳方法是什么？

每次添加新边时，我是否都必须检查整个图中的循环？这种方法没有利用已经进行的计算。有没有我还没有找到的算法？

谢谢。

Answer 1

您可以使用此处的快速联合查找算法来首先检查新边的两端是否已经连接。

编辑：
如评论中所述，此解决方案仅适用于无向图。对于有向图，以下链接可能会有所帮助https://cs.stackexchange.com/questions/7360/directed-union-find。