python - 跟踪周期，同时向稀疏图中添加随机边

Question

场景:我有一个图，表示为节点 (0...n) 的集合。该图中没有边。

对于该图，我随机连接节点，一次一个。另一种说法是我向图中添加随机边，一次一个。

我不想在此图中创建简单的循环。

当我添加随机边缘时，是否有一种简单和/或非常有效的方法来跟踪循环的创建？使用图遍历，这很容易，因为我们只需要跟踪单个路径的两个末端节点。但是，在这种情况下，我们需要跟踪任意数量的路径 - 有时这些路径组合成更大的路径，我们也需要跟踪它。

我尝试了几种方法，主要归结为维护“外部节点”列表和它们内部的一组节点，然后当我添加一条穿过它的边并更新它时。但是，它变得非常复杂，特别是如果我删除图中的一条边。

我试图搜索相关的算法或讨论，但我找不到任何东西。我知道我可以使用 BFS 来检查循环，但是在每次添加边之后，BFS 的效率非常低。

Answer 1

我在淋浴时想出的可能解决方案。

我要做的是维护一个大小为 n 的列表，表示该节点在边缘上的次数。

当我添加一条边 (i,j) 时，我将递增 list[i] 和 list[j]。

如果在添加边之后，list[i] > 1，并且 list[j] > 1，我将从该边开始执行 DFS。

我意识到我不需要 BFS，我只需要从最后添加的边开始进行 DFS，并且只有在它至少有可能处于一个循环中(它的节点出现两次)时我才需要这样做。

我怀疑这是最优的..也许某种不相交集的列表会更好。但这比我之前想到的要好得多。