有向无环加权图中两个随机节点的连接

Question

总结

因此，我有一个有向无环加权图，其中每条边都有一个输入和输出节点，每个节点都有一个ID，我使用一个字典将所有传入的边映射到一个节点的ID，并使用另一个字典对所有传出的边进行同样的操作，这样，当出现节点ID时，我可以在大约O(1)时间内告诉所有传入和传出的边。

要求

我需要能够添加新的随机边(即连接两个随机节点)，以保证无论图有多大，它都不会有任何循环。

我试过的

由于我完全控制如何构建我的图，我可以拓扑地对它进行排序，并使用卡恩算法来计算对于两个均匀随机选择的节点N1和N2，图是否将导致O（n）时间的循环。问题是，如果它这样做呢？我必须尝试一个新的随机对并重复这个过程，直到我幸运为止。这听起来好像它会与图形一起变得非常糟糕，因为图形的边缘密度越大，一个新的随机图形就越有可能创建一个循环。

我也读过这篇文章:生成一个随机DAG，这在本质上与我的问题类似，但是，由于我对这个问题的其他限制，我不能使用建议的解决方案来基于它们的id连接节点，并且只能连接较小的到较大的id(之前有新节点的节点)。

问题

有没有办法设计一种结构，只允许我在节点之间随机选择，如果通过新的边缘连接，则不会产生与内存开销无关的周期？这应该是 O（1） 操作。

Answer 1

我有一个O（1）解决方案来检查是否可以在图形中包含边。但是，需要最坏情况的O（n）才能插入边缘。

你可以维护一个二进制可达性矩阵R，其中R[u，v]=1，如果你可以从当前图中的u到达v，R[u，v]=0，如果不是。R最初可以使用Floyd-Warshall计算一次。

如果你想检查是否可以包含一个边缘（u，v），你现在只需要检查R[v，u] = 0。如果它是R[v，u] = 1，则通过插入（u，v）来构造一个圆。

剩下的问题是更新此结构。如果您最终将边缘（u， v）插入图中，您将设置R[u， v]=1。此外，所有能够到达u（R[：， u]=1）的节点现在都能够到达v（R[v，：]=1）可访问的所有节点。因此，您需要设置您的条目R[i， j]=1如果R[i， u]=1和R[v： j]=1。

不幸的是，在最坏的情况下，更新步骤需要O(n)。在实践中，当图形仍然相当稀疏时，您应该能够利用稀疏矩阵表示(对于每行< code>u具有索引< code>v的散列列表，其中< code>R[u，v] = 1)来有效地实现这一点，并且要快得多。

如果要随机选择可能的边，则必须通过相同的结构另外维护和更新可能边的列表。