c++ - 生成随机约束图

Question

我需要生成一个具有固定顶点数的随机图。我每次都很难找到解决方案。

图形规则

1. 每个顶点将有一个随机数量的连接，最多为 N-1，其中 N 是顶点的总数。
2. 顶点不能包含与自身的直接连接
3. 顶点不能包含与其他顶点的重复连接。
4. 如果顶点 A 连接到顶点 B，则顶点 B 必须连接到顶点 A。
5. 每个顶点必须连接到至少 3 个其他顶点。所以每个顶点将有 [3,N-1] 条边。

我大约有 70% 的时间得到了正确的解决方案，但其他时候我在图中走得很远，然后就没有有效的顶点了。我需要对顶点连接有什么约束才能保证解决方案？

目前我在做什么

1. 为 [3,N-1] 之间的每个顶点随机分配一些连接。
2. 检查连接总数是否为偶数。如果 A 指向 B，B 指向 A，那么图中的连接总数应该是偶数，否则无解。如果是奇数，修改一个顶点，使总数为偶数。
3. 填写每个完全约束的顶点。因此，具有 N-1 个连接的顶点必须指向所有其他顶点。填充从该顶点到所有其他顶点的连接，并为所有其他顶点提供到完全约束顶点的连接。
4. 根据约束的严格程度处理每个顶点。因此，通过生成的随机顶点索引处理所有具有 N-2 个连接、N-3 个连接、N-4 等的顶点。
5. 如果新的随机索引有效，则连接它们然后继续，如果无效，则重新随机索引，直到获得有效值。 (图表最多只有 7-15 个节点，所以这不会花费很长时间)。

通常我会到达最后 2 个顶点，但此方法没有留下任何有效值。每个都需要 1 个连接，但它们已经相互连接。谁有更好的算法或对连接值数量的额外限制可以帮助我？

假设有偶数条边，应该有很多解，但我上面的算法显然不能保证找到一个。

Answer 1

1. 创建一个包含少于 3 条边的所有顶点的 vector 。
2. 从 vector 中随机选择一个顶点。
3. 复制删除所选顶点的 vector (您可以交换所选顶点和最后一个顶点并调整大小)。
4. 同时删除所有已连接到所选顶点的目标顶点。
5. 从复制的 vector 中选择一个顶点，并在两个选择的n个顶点之间的每个方向上创建一条边
6. 重复步骤 1..5，只要少于 3 条边的所有顶点的 vector 不为空