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

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不能遍历集群外部。

我认为这可能会起作用，虽然拓扑结构不会是真正的随机性，但它会像一个由连接在一起的较小图形组成的大循环一样循环。但根据您需要测试的算法，这可能派上用场。

编辑：

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