在有向无环加权图中连接两个随机节点
Connecting Two Random Nodes in a Directed Acyclic Weighted Graph
总结
所以我有一个有向无环加权图，其中每条边都有一个输入和输出节点，每个节点都有一个 ID，我使用字典将所有传入边通过其 ID 映射到一个节点，另一个节点执行相同的操作对于所有传出边，所以当出现节点 ID 时，我可以在 ~O(1) 时间内告诉所有传入和传出边。
要求
我需要能够添加新的随机边（即连接两个随机节点），确保无论图有多大，它都不会有任何循环。
我试过的
由于我完全控制如何构建我的图，我可以对其进行拓扑排序并使用 Kahn 算法来确定对于两个均匀随机选择的节点 N1 和 N2，该图是否会在 O(n ） 时间。问题是如果它发生了怎么办？我必须尝试一对新的随机配对并重复这个过程，直到我走运为止。这听起来好像它会严重影响图形，因为图形的边缘越密集，新的随机图形就越有可能创建一个循环。
我也读过这个post：
Generating a random DAG
，这在本质上与我的问题相似，但是，由于其他限制，我无法使用建议的解决方案根据节点的 ID 连接节点，并且只能连接较小的 ID 和较大的 ID（之前出现的节点和新节点）我有问题。
问题
有没有一种方法可以设计一个只允许我在节点之间随机选择的结构none，如果通过新边连接，将产生一个与内存开销无关的循环？这应该是一个 O(1) 操作。
我有一个 O(1) 解决方案来检查图中是否可以包含一条边。但是，插入边缘需要 worst-case 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,u] = 1 和 R[v:j] = 1.
，则需要设置条目 R[i, j] = 1
不幸的是，在最坏的情况下，更新步骤将花费 O(n)。在实践中，当图形仍然相当稀疏时，您应该能够使用稀疏矩阵表示有效地实现这一点（哈希列表，每行 u 的索引 v，其中 R[u, v] = 1）并且要多更快。
如果您想随机 select 一条可能的边，您将不得不通过相同的结构另外维护和更新可能的边列表。
总结
所以我有一个有向无环加权图，其中每条边都有一个输入和输出节点，每个节点都有一个 ID，我使用字典将所有传入边通过其 ID 映射到一个节点，另一个节点执行相同的操作对于所有传出边，所以当出现节点 ID 时，我可以在 ~O(1) 时间内告诉所有传入和传出边。
要求
我需要能够添加新的随机边（即连接两个随机节点），确保无论图有多大，它都不会有任何循环。
我试过的
由于我完全控制如何构建我的图，我可以对其进行拓扑排序并使用 Kahn 算法来确定对于两个均匀随机选择的节点 N1 和 N2，该图是否会在 O(n ） 时间。问题是如果它发生了怎么办？我必须尝试一对新的随机配对并重复这个过程，直到我走运为止。这听起来好像它会严重影响图形，因为图形的边缘越密集，新的随机图形就越有可能创建一个循环。
我也读过这个post： Generating a random DAG ，这在本质上与我的问题相似，但是，由于其他限制，我无法使用建议的解决方案根据节点的 ID 连接节点，并且只能连接较小的 ID 和较大的 ID（之前出现的节点和新节点）我有问题。
问题
有没有一种方法可以设计一个只允许我在节点之间随机选择的结构none，如果通过新边连接，将产生一个与内存开销无关的循环？这应该是一个 O(1) 操作。
我有一个 O(1) 解决方案来检查图中是否可以包含一条边。但是，插入边缘需要 worst-case 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,u] = 1 和 R[v:j] = 1.
R[i, j] = 1
不幸的是，在最坏的情况下，更新步骤将花费 O(n)。在实践中，当图形仍然相当稀疏时，您应该能够使用稀疏矩阵表示有效地实现这一点（哈希列表，每行 u 的索引 v，其中 R[u, v] = 1）并且要多更快。
如果您想随机 select 一条可能的边，您将不得不通过相同的结构另外维护和更新可能的边列表。