生成大型（约 300k 个顶点）随机平面图（这里的“随机”意味着均匀分布）的最有效方法是什么？
您看过玻尔兹曼采样吗？请参阅 Eric Fusy 的论文“线性时间内平面图的均匀随机采样”。该论文和实现可以在他的主页中找到，论文称可以在几秒钟内生成大小为 100K 的实例。
另一种可能性是随机选择坐标，然后计算 Delaunay 三角剖分，这是一个平面图（看起来也不错）。请参阅 http://en.wikipedia.org/wiki/Delaunay_triangulation 有 O(n log(n)) 算法来计算此类三角剖分。
如果没有任何其他要求，我会说查找随机迷宫生成。如果您想要图表中存在循环，请从简单的迷宫中随机移除一些墙壁。迷宫中的交叉点成为图形中的节点，移除的墙壁是边缘。这意味着您可以通过选择迷宫的大小来选择节点的数量。
迷宫通常是在二维网格上完成的，从一个点到另一个点最多有 4 个连接，但是没有什么可以阻止你在六角形瓷砖或其他东西上做迷宫。
如果均匀是指在空间中均匀分布，那么这是我为空间生态/进化模拟器生成平面图而开发的一个相当快的算法。它将生成具有您指定的预期度数的随机平面图，当然也会有一些变化。如果您希望在平面图中使用统一的随机度数，则可以扩展它以根据均匀的随机数选择预期的度数。
https://github.com/briandconnelly/seeds/blob/master/seeds/plugins/topology/CartesianTopology.py
一种方法是尝试生成一个随机图，它满足与平面图类似的约束（例如，边<= 3*vertices - 6) and check if it is planar in O(n) time using Tarjan's planarity testing algorithm. If it is not planar, generate again. Not sure how efficient this would be for 300K vertices!, though (or if it will even give you graphs with uniform probability).
有一些关于生成平面图的文献，我可以在这里找到一篇论文：生成带标签的平面图，它显然期望 O(n^4) 运行时间，并且可能也不值得。也许那里的参考资料会帮助您找到可能有帮助的东西。
祝你好运！
我不知道，“均匀分布”是什么意思？
我使用以下代码（PHP）来生成随机最大平面图。如果您不想获得非最大平面图，则必须删除某些连接。 （我不认为该算法有效。可能不需要边缘的计算。使用存储管理和索引绝对可以做得更好[array_keys，shuffle，...]。但它适用于我的箱子较小。）
class MapGenerator
{
protected const MINIMUM_CONST = 3;
protected const MINIMUM_MAP = [
1 => [
self::KEY_CONNECT => [2, 3], // connect to every node in the triangle
],
2 => [
self::KEY_CONNECT => [3, 1],
],
3 => [
self::KEY_CONNECT => [1, 2],
],
];
protected const KEY_MINIMUM_MAP = '1-2-3';
const KEY_CONNECT = 'connect';
public function generatePlanarMap($nodeCounts = 10)
{
$this->map = self::MINIMUM_MAP;
$this->areas = [self::KEY_MINIMUM_MAP => []];
if ($nodeCounts > self::MINIMUM_CONST) {
/** @var int $newNode */
for ($newNode = self::MINIMUM_CONST + 1; $newNode <= $nodeCounts; $newNode++) {
$myKeys = array_keys($this->areas);
shuffle($myKeys);
$randomArea = $myKeys[0];
// remove the selected area, which will be splitted up to three new areas by including the new node
unset($this->areas[$randomArea]);
$listTriangleNodes = $this->decodeAreaToKeys($randomArea);
$this->map[] = [
self::KEY_CONNECT => $listTriangleNodes,
];
$newNodeKey = count($this->map);
$this->map[$listTriangleNodes[0]][self::KEY_CONNECT][] = $newNodeKey;
$this->map[$listTriangleNodes[1]][self::KEY_CONNECT][] = $newNodeKey;
$this->map[$listTriangleNodes[2]][self::KEY_CONNECT][] = $newNodeKey;
// detect the three new triagulations, which are generated by the new node
foreach ([[0, 1], [1, 2], [0, 2]] as $variation) {
// I have not tested this part
$this->areas[$this->defineKeyForArea($newNodeKey, $listTriangleNodes[$variation[0]], $listTriangleNodes[$variation[1]])] = [
self::KEY_CONNECT => [
($newNodeKey < $listTriangleNodes[$variation[0]] ? [$newNodeKey, $listTriangleNodes[$variation[0]],] : [$listTriangleNodes[$variation[0]], $newNodeKey,]),
($newNodeKey < $listTriangleNodes[$variation[1]] ? [$newNodeKey, $listTriangleNodes[$variation[1]],] : [$listTriangleNodes[$variation[1]], $newNodeKey,]),
($listTriangleNodes[$variation[0]] < $listTriangleNodes[$variation[1]] ? [$listTriangleNodes[$variation[0]], $listTriangleNodes[$variation[1]],] : [$listTriangleNodes[$variation[1]], $listTriangleNodes[$variation[0]],]),
],
];
}
}
}
$this->areas[self::KEY_MINIMUM_MAP] = [
self::KEY_CONNECT => [[1, 2], [1, 3], [2, 3],],
];
}
protected function decodeAreaToKeys(string $area)
{
return explode('-', $area);
}
}
备注：每个生成的图都满足四色定理，因为每个节点的颜色可以通过图的生成来定义。我试图找到一种算法，它可以通过从随机节点开始并且不知道生成来对图进行着色。直到现在我还没有成功。