Java 如何生成随机图？

How to generate random graphs?

提问by bourbaki4481472

I want to be able to generate random, undirected, and connected graphs in Java. In addition, I want to be able to control the maximum number of vertices in the graph. I am not sure what would be the best way to approach this problem, but here are a few I can think of:

我希望能够在 Java 中生成随机、无向和连通图。另外，我希望能够控制图中的最大顶点数。我不确定解决这个问题的最佳方法是什么，但这里有一些我能想到的：

(1) Generate a number between 0and nand let that be the number of vertices. Then, somehow randomly link vertices together (maybe generate a random number per vertex and let that be the number of edges coming out of said vertex). Traverse the graph starting from an arbitrary vertex (say with Breadth-First-Search) and let our random graph Gbe all the visited nodes (this way, we make sure that Gis connected).

(1) 在0和之间生成一个数字，n并将其作为顶点数。然后，以某种方式将顶点随机链接在一起（可能为每个顶点生成一个随机数，并将其设为从所述顶点出来的边数）。从任意顶点开始遍历图（比如广度优先搜索），让我们的随机图G是所有访问过的节点（这样，我们确保G连接）。

(2) Generate a random square matrix (of 0's and 1's) with side length between 0and n(somehow). This would be the adjacency matrix for our graph (the diagonal of the matrix should then either be all 1's or all 0's). Make a data structure from the graph and traverse the graph from any node to get a connected list of nodes and call that the graph G.

(2) 生成一个随机方阵（由0's 和1's 组成），边长在0和之间n（不知何故）。这将是我们图的邻接矩阵（矩阵的对角线应该是 all1或 all 0）。从图中创建一个数据结构并从任何节点遍历该图以获得连接的节点列表并将其称为图G。

Any other way to generate a sufficiently random graph is welcomed. Note: I do not need a purely random graph, i.e., the graph you generate doesn't have to have any special mathematical properties (like uniformity of some sort). I simply need lots and lots of graphs for testing purposes of something else.

欢迎任何其他生成足够随机图的方法。注意：我不需要纯随机图，即您生成的图不必具有任何特殊的数学属性（例如某种均匀性）。我只需要大量的图表来测试其他东西。

Here is the Java Nodeclass I am using:

这是Node我正在使用的 Java类：

public class Node<T> {
    T data;
    ArrayList<Node> children= new ArrayList<Node>();
    ...}

Here is the Graphclass I am using (you can tell why I am only interested in connected graphs at the moment):

这是Graph我正在使用的类（你可以告诉我为什么我现在只对连通图感兴趣）：

public class Graph {
    Node mainNode;
    ArrayList<Node> V= new ArrayList<Node>();

    public Graph(Node node){
        mainNode= node;
    }
    ...}

As an example, this is how I make graphs for testing purposes right now:

例如，这就是我现在制作用于测试目的的图表的方式：

    //The following makes a "kite" graph G (with "a" as the main node).
    /*     a-b
           |/|
           c-d
    */
    Node<String> a= new Node("a");
    Node<String> b= new Node("b");
    Node<String> c= new Node("c");
    Node<String> 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);

采纳答案by Vincent Labatut

Whatever you want to do with your graph, I guess its density is also an important parameter. Otherwise, you'd just generate a set of small cliques (complete graphs) using random sizes, and then connect them randomly.

无论你想用你的图表做什么，我想它的密度也是一个重要的参数。否则，您只需使用随机大小生成一组小集团（完整图），然后随机连接它们。

If I'm correct, I'd advise you to use the Erd?s-Rényi model: it's simple, not far from what you originally proposed, and allows you to control the graph density (so, basically: the number of links).

如果我是对的，我建议您使用Erd?s-Rényi 模型：它很简单，与您最初提出的不远，并且允许您控制图密度（因此，基本上：链接数） .

Here's a short description of this model:

下面是这个模型的简短描述：

1. Define a probability value p (the higher p and the denser the graph: 0=no link, 1=fully connected graph);
2. Create your n nodes (as objects, as an adjacency matrix, or anything that suits you);
3. Each pair of nodes is connected with a (independent) probability p. So, you have to decide of the existence of a link between them using this probability p. For example, I guess you could ranbdomly draw a value q between 0 and 1 and create the link iff q < p. Then do the same thing for each possible pair of nodes in the graph.

1. 定义一个概率值p（p越高，图越密：0=无链接，1=全连接图）；
2. 创建你的 n 个节点（作为对象，作为邻接矩阵，或者任何适合你的东西）；
3. 每对节点都以（独立的）概率 p 连接。因此，您必须使用此概率 p 来确定它们之间是否存在链接。例如，我猜你可以随意地在 0 和 1 之间绘制一个值 q 并创建链接 iff q < p。然后对图中的每个可能的节点对执行相同的操作。

With this model, if your p is large enough, then it's highly probable your graph is connected (cf. the Wikipedia reference for details). In any case, if you have several components, you can also force its connectedness by creating links between nodes of distinct components. First, you have to identify each component by performing breadth-first searches (one for each component). Then, you select pairs of nodes in two distinct components, create a link between them and consider both components as merged. You repeat this process until you've got a single component remaining.

使用此模型，如果您的 p 足够大，那么您的图很有可能是连通的（请参阅维基百科参考以了解详细信息）。在任何情况下，如果您有多个组件，您还可以通过在不同组件的节点之间创建链接来强制其连通性。首先，您必须通过执行广度优先搜索（每个组件一个）来识别每个组件。然后，您选择两个不同组件中的节点对，在它们之间创建链接并将两个组件视为合并。重复这个过程，直到剩下一个组件。

回答by j_random_hacker

The only tricky part is ensuring that the final graph is connected. To do that, you can use a disjoint set data structure. Keep track of the number of components, initially n. Repeatedly pick pairs of random vertices u and v, adding the edge (u, v) to the graph and to the disjoint set structure, and decrementing the component count when the that structure tells you u and v belonged to different components. Stop when the component count reaches 1. (Note that using an adjacency matrix simplifies managing the case where the edge (u, v) is already present in the graph: in this case, adj[u][v] will be set to 1 a second time, which as desired has no effect.)

唯一棘手的部分是确保最终图形是连接的。为此，您可以使用不相交的集合数据结构。跟踪组件的数量，最初是 n。重复选择随机顶点 u 和 v 对，将边 (u, v) 添加到图形和不相交的集合结构中，并在该结构告诉您 u 和 v 属于不同组件时递减组件计数。当组件计数达到 1 时停止。（请注意，使用邻接矩阵可以简化管理图中边 (u, v) 已经存在的情况：在这种情况下，adj[u][v] 将设置为 1第二次，根据需要没有效果。）

If you find this creates graphs that are too dense (or too sparse), then you can use another random number to add edges only k% of the time when the endpoints are already part of the same component (or when they are part of different components), for some k.

如果您发现这会创建过于密集（或过于稀疏）的图，那么您可以使用另一个随机数在端点已经是同一组件的一部分时（或当它们是不同组件的一部分时）仅在 k% 的情况下添加边组件），对于一些 k。