向稀疏图中添加随机边时跟踪循环
场景:我有一个图，表示为节点的集合(0.n)。这张图中没有边。
在这个图中，我随机连接节点，每次连接一个节点。另一种说法是，我在图中添加随机边，一次加一条。
我不想在这个图中创建简单的循环。
在我添加随机边时，是否有一种简单和/或非常有效的方法来跟踪循环的创建？使用图遍历，很容易，因为我们只需要跟踪单个路径的两个端节点。但是，在这种情况下，我们有很多需要跟踪的路径--有时这些路径组合成一条更大的路径，我们也需要跟踪这些路径。
我尝试过几种方法，这些方法主要是维护“外部节点”列表以及它们内部的一组节点，然后当我在其中添加一个边缘并对其进行更新时。但是，它变得非常复杂，特别是如果我去掉了图中的一个边。
我试图搜索算法或讨论这一点，但我真的找不到任何东西。我知道我可以做一个BFS来检查周期，但是在每次添加边缘之后，BFS的效率都是如此之低。
回答 2
Stack Overflow用户
发布于 2018-03-17 09:36:30
我在洗澡时想出了可能的解决方案。
我要做的是保持一个n大小的列表，表示该节点在边缘上的次数。
当我添加边(i，j)时，我将增加listi和listj。
如果在添加了edge之后，listi > 1，listj > 1，我将从该边开始执行DFS。
我意识到我不需要BFS，我只需要从上一个添加的边缘开始进行DFS，而且我只需要在它至少有可能在一个周期中出现(它的节点出现两次)时才需要这样做。
我怀疑这是最好的..。也许某种不相交的集合会更好。但这比我以前想过的任何事情都要好。
Stack Overflow用户
发布于 2018-03-20 05:27:25
如果跟踪图形中已连接的组件，则可以测试插入的每个边缘是否已包含在同一组件中。如果是的话，那么你插入的边会给你的图引入一个循环。
看看这篇文章，这篇文章似乎对如何做到这一点提供了一些很好的参考：https://cstheory.stackexchange.com/questions/2548/is-there-an-online-algorithm-to-keep-track-of-components-in-a-changing-undirecte
https://stackoverflow.com/questions/49339575
复制
相似问题
c++中的delete vs NULL vs free
删除vs delete[]
批量删除(truncate vs delete)
new char [] vs new char()，delete() vs delete []
正确使用C++中关于char *的delete vs delete[ ]
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
