如何生成随机图？
我希望能够在Java中生成随机，无向和连接的图形。 另外，我希望能够控制图中的最大顶点数。 我不确定解决这个问题的最佳方法是什么，但这里有一些我能想到的：
（1）生成一个介于0和n之间的数字，并将其作为顶点数。 然后，以某种方式将顶点随机链接在一起（可能每个顶点生成一个随机数，并将其作为从所述顶点出来的边数）。 从任意顶点开始遍历图形（比如使用广度优先搜索），让随机图G成为所有访问节点（这样，我们确保G连接）。
（2）生成一个边长在0到n之间的随机方阵（ 0和1 ）（不知何故）。 这将是我们图形的邻接矩阵（矩阵的对角线应该全部为1或全部为0 ）。 从图形中创建数据结构并从任何节点遍历图形以获得连接的节点列表并将其称为图形G
任何其他生成足够随机图的方法都受到欢迎。 注意 ：我不需要纯随机图，即，您生成的图不必具有任何特殊的数学属性（如某种均匀性）。 我只需要很多很多图表来测试其他东西。
这是我正在使用的Java Node类：
public class Node { T data; ArrayList children= new ArrayList(); ...}
这是我正在使用的Graph类（你可以告诉我为什么我现在只对连接图感兴趣）：
public class Graph { Node mainNode; ArrayList V= new ArrayList(); public Graph(Node node){ mainNode= node; } ...}
例如，这就是我现在为测试目的制作图表的方法：
//The following makes a "kite" graph G (with "a" as the main node). /* ab |/| cd */ Node a= new Node("a"); Node b= new Node("b"); Node c= new Node("c"); Node d= new Node("d"); a.addChild(b); a.addChild(c); b.addChild(a); b.addChild(c); b.addChild(d); c.addChild(a); c.addChild(b); c.addChild(d); d.addChild(c); d.addChild(b); Graph G1= new Graph(a);
无论你想用图表做什么，我猜它的密度也是一个重要的参数。 否则，您只需使用随机大小生成一组小团队（完整图表），然后随机连接它们。
如果我是正确的，我建议你使用Erdős-Rényi模型 ：它很简单，与你最初提出的模型相差不远，并允许你控制图形密度（所以，基本上：链接的数量）。
以下是此型号的简短说明：
- 定义概率值p（图形越高，密度越大：0 =无链接，1 =完全连接图形）;
- 创建你的n个节点（作为对象，作为邻接矩阵，或任何适合你的东西）;
- 每对节点以（独立的）概率p连接。 因此，您必须使用此概率p来确定它们之间是否存在链接。 例如，我猜你可以在0和1之间绘制一个值q并创建链接iff q
使用此模型，如果您的p足够大，那么您的图形很可能已连接（请参阅Wikipedia参考以获取详细信息）。 在任何情况下，如果您有多个组件，还可以通过在不同组件的节点之间创建链接来强制其连接性。 首先，您必须通过执行广度优先搜索（每个组件一个）来识别每个组件。 然后，在两个不同的组件中选择节点对，在它们之间创建链接并将两个组件视为合并。 重复此过程，直到剩下单个组件。
唯一棘手的部分是确保最终图形连接。 为此，您可以使用不相交的集数据结构 。 跟踪组件的数量，最初是n。 重复选择一对随机顶点u和v，将边（u，v）添加到图形和不相交的集合结构中，并在该结构告诉你u和v属于不同的组件时减少组件计数。 当组件计数达到1时停止。（请注意，使用邻接矩阵可以简化管理图中已存在边（u，v）的情况：在这种情况下，adj [u] [v]将设置为1第二次，根据需要没有效果。）
如果您发现这会创建太密集（或太稀疏）的图形，那么您可以使用另一个随机数来仅在端点已经是同一组件的一部分时（或当它们是不同组件的一部分时）的k％时间添加边组件），对于某些k。