给定一组顶点，如何生成具有接近最少边数的强连通有向图？

Question

我正在尝试对我的图形类的 dijkstras 算法进行测试。为此，我生成一个具有数千个顶点的图，然后通过随机添加数千条边来连接该图，直到该图连接为止。然后，我可以在任意两个随机顶点之间反复运行搜索，并确保它们之间存在路径。问题是，我经常得到一个近乎密集的图，因为我使用邻接列表表示，导致我的搜索算法非常慢。

问题： 给定一组顶点 V，如何生成强连接的有向图，该图的边数明显少于相同顶点上的稠密图的边数？

我正在考虑简单地执行以下操作：

vertex 1 <--> vertex 2, vertex 2 <--> vertex 3, ..., vertex n-1 <--> vertex n

然后在整个图中随机添加 n/10 个边，但这似乎不是提出随机图结构来测试我的搜索算法的最佳方法。

Answer 1

一种方法是维护一组强连接组件（从

|V|

单顶点组件开始），并在每次迭代中，通过将每个组件的随机顶点连接到下一个的随机顶点，形成一个循环。

这往往会生成非常稀疏的图，因此根据您的用例，您可能还想添加一些额外的随机边。

编辑：直观上，我认为在决定在一次迭代中合并多少个组件时，您会希望使用指数分布。不过，我对此没有任何真正的支持。

Answer 2

我不知道是否有更好的方法，但至少这似乎有效：

• 我会在随机顶点之间添加 E（有向）边。这将生成几个顶点簇。
• 然后，我需要连接这些集群以形成集群链，从而确保从一个集群我可以到达任何其他集群。为此，我可以将每个簇的随机顶点标记为“主”顶点，并将主顶点加入形成循环。因此，您有一个由簇（还不是顶点）组成的强连接有向图。最后一个主设备应连接回第一个主设备，从而创建一个环路。
• 现在，为了将其变成由 顶点 组成的强连通有向图，我需要使每个簇本身成为强连通有向图。但是，如果我从集群的主节点开始运行 DFS，并且每次找到叶子时，我都会从该叶子添加一条边到其主顶点，这很容易。请注意，DFS 不得遍历集群之外。

我认为这可能有效，尽管拓扑不会真正随机，但它会像由较小的图连接在一起组成的大循环一样循环。但根据您需要测试的算法，这可能会派上用场。

编辑：

• 如果之后您想要拥有更随机的拓扑，您可以在不同簇的顶点之间添加随机边。这不会使规则无效并为您的算法创建更复杂的遍历路径。

Answer 3

采用具有 $m\le n$ 个节点的随机连通无向图，然后用有向循环替换每条边。

在极端情况下，无向图将是一棵生成树，其边被一对反平行弧取代；因此 $2(n-1)$ 是可能的最小弧数。