我正在尝试生成一个无向图，其中每个节点都有与之关联的最大度数。也就是说，如果一个节点的最大度数为 2，则它最多可以连接两个节点（允许连接的节点，但不允许为 0）。我的问题是我正在尝试生成一个可以从一个节点到另一个节点的图。目前，我可以让节点“随机”相互连接，但问题是它可以创建分割图，即如果你有 10 个节点，那么有时会不经意地形成每个 5 个节点的两个图。如果有人知道有效的解决方案，我很想听听！
编辑：假设我有一个包含十个节点的图，并且我指定最大度数为 2。在这种情况下，这是可取的：
而这是我试图避免的：
两个图的每个节点的最大度数均为 2，但在第二张图像中，不可能选择任意节点并能够到达任何其他任意节点。
这个问题在图论中是一个非常有名的问题，可以在多项式时间内求解，我忘记了它的名字（可能是“根据其度数序列找到一个图”）。无论如何，Király 的解决方案是一个很好的方法，这里比我解释得更好。该算法解决了满足给定度数序列的精确图，但它应该很容易修改为您更松散的约束。
显而易见的解决方案是将其构建为 N 路树——如果最大度数为 2，则最终得到一棵二叉树。
为了使其无向，您不仅有指向“子”节点的指针，还有指向“父”节点的反向指针。至少据推测，那个不计入节点的度数（如果是这样，你的度数为二基本上最终成为一个双向链接的线性列表而不是一棵树）。
编辑：澄清后，似乎后者确实如此。尽管它们的绘制方式不同（链接指向不同的方向），但显示所需结果的第一张图片在拓扑上只是一个线性链表。如上所述，由于您想要一个无向图，因此它最终成为一个双向链表。
听起来您已经知道图表应该是什么样子了，所以我相信您是否可以使用深度优先搜索方法。尽管可以使用呼吸优先搜索来避免递归。
例如，如果您有节点 1-5，并且 k=2，那么您可以通过从节点 1 开始构建图，然后简单地随机选择一个未访问的节点。像这样：
1 [Start at 1]
1-2 [expand 2, add edge(1,2) to graph]
1-2-3 [expand 3, add edge(2,3) to graph]
1-2-3-4 [expand 4, add edge(3,4) to graph]
1-2-3-4-5 [expand 5, add edge(4,5) to graph]
1-2-3-4-5-1 [expand 1, add edge(5,1) to graph] (this step may or may not be done)
如果一条边从未被使用过两次，那么 p 条路径将导致总体度数为 p*2，起始节点和结束节点的度数取决于路径是否真的是一条路径。为了避免重复工作，可能更容易将顶点标记为整数 1 到 N，然后创建边，使得每个顶点 v 连接到编号为 (v+j) mod (N+1) 的顶点，其中 j和 (N+1) 互质< N-1。最后一点让事情变得有点问题，因为如果 N 不是素数，则从 1 到 N 的共素数的数量可能会受到限制。这意味着对于某些值不存在解决方案，至少以新的哈密顿路径/旅行的形式存在。但是，如果您忽略互质方面并简单地将 j 设为从 1 到 p 的整数，然后遍历每个顶点并创建边（而不是使用路径方法），您可以使所有顶点的度数为 k，其中k 是一个偶数 >= 2。这在 O(N*k) 中是可以实现的，尽管如果使用互质法，它可能会被推回 O(N^2)。
因此，如果从 1 开始，j=2，k=4 的路径将如下所示：
1 [Start at 1]
1-3 [expand 3, add edge(1,3) to graph]
1-3-5 [expand 5, add edge(3,5) to graph]
1-3-5-2 [expand 2, add edge(5,2) to graph]
1-3-5-2-4 [expand 4, add edge(2,4) to graph]
1-3-5-2-4-1 [expand 1, add edge(4,1) to graph] (this step may or may not be done)
由于 |V| = 5 和 k = 4，得到的边形成一个完整的图，这是预期的。由于 2 和 5 是互质数，因此它也可以解决。
获得奇数学位有点困难。首先获得度数 k-1，然后以这样的方式添加边缘，从而获得整体奇数度。似乎很容易接近（有一个或两个例外）为奇数度的所有边，但对于奇数个顶点似乎不可能或至少非常困难，并且需要仔细选择具有偶数个顶点的边. 其中的部分，不容易放入算法中。但是，它可以通过简单地选择两个未使用的顶点并在它们之间创建一条边来近似，这样顶点不会被使用两次，并且边不会被使用两次。