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

Question

总结

所以我有一个有向非循环加权图，其中每条边都有一个输入和输出节点，每个节点都有一个 ID，我使用字典将所有传入边通过其 ID 映射到一个节点，另一个对所有节点执行相同的操作传出边，所以当出现节点 ID 时，我可以在 ~O(1) 时间内告诉所有传入和传出边。

要求

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

我尝试过的

由于我完全控制如何构建我的图，我可以对其进行拓扑排序并使用 Kahn 算法来确定对于两个均匀随机选择的节点 N1 和 N2，该图是否会在 O(n) 时间内产生一个循环.问题是如果它发生了怎么办？我必须尝试一对新的随机配对并重复这个过程，直到我走运为止。这听起来好像它会严重影响图形的缩放，因为图形的边缘越密集，新的随机图形就越有可能创建一个循环。

我也看过这篇文章: Generating a random DAG，这在本质上与我的问题相似，但是，由于其他限制，我无法使用建议的解决方案根据节点的 ID 连接节点，并且只能连接较小的 ID 和较大的 ID(之前出现的节点和新节点)我有问题。

问题

有没有一种方法可以设计一个只允许我在节点之间随机选择的结构，如果通过新边连接，则不会产生与内存开销无关的循环？这应该是一个 O(1) 操作。

Answer 1

我有一个O(1) 解决方案来检查图中是否可以包含一条边。然而，在最坏的情况下，插入边缘需要 O(n)。

您可以维护一个二进制可达性矩阵 R其中 R[u, v]=1如果你能打到v来自 u在你当前的图表和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)。在实践中，当图形仍然相当稀疏时，您应该能够使用稀疏矩阵表示(带有索引的哈希列表 v 对于每一行 u ，其中 R[u, v] = 1 )有效地实现它并且更快。

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