2

概括

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

要求

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

我试过的

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

我还阅读了这篇文章： 生成随机 DAG ，这在本质上与我的问题相似，但是，我不能使用建议的解决方案来根据节点的 ID 连接节点，而只能连接较小的 ID（之前的节点）由于我对这个问题有其他限制，所以节点是新的）。

问题

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

4

1 回答 1

2

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

您可以维护一个二进制可达性矩阵R，R[u, v]=1如果您可以v从u当前图表中访问，R[u, v]=0如果不能。R最初可以使用Floyd-Warshall计算一次。

如果你想检查是否可以包含一个边缘(u,v)，你现在只需要检查 if R[v, u] = 0。如果是，R[v, u] = 1您正在通过插入(u,v).

剩下的问题变成了更新这个结构。如果您最终将边缘(u, v)插入到图中，您将设置R[u, v] = 1. 此外，能够到达 ( ) 的所有节点现在都能够到达( u)R[:,u]=1可到达的所有节点。因此，您将需要设置您的条目if和.vR[v,:] = 1R[i, j] = 1R[i,u] = 1R[v:j] = 1

不幸的是，在最坏的情况下，更新步骤将花费 O(n)。在实践中，当图形仍然相当稀疏时，您应该能够使用稀疏矩阵表示（具有v 每行uwhere的索引的哈希列表R[u, v] = 1）有效地实现这一点，并且速度要快得多。

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

于 2019-07-03T11:10:23.983 回答