如何生成随机图？ [英] How to generate random graphs?

问题描述

我希望能够生成随机，无向，并连通图中的Java。此外，我希望能够控制图中的顶点的最大数量。我不知道什么是处理这个问题的最好办法，但这里有一些我能想到的：

（1）生成一个号码之间的 0 和 N 键，那一定是顶点的数目。然后，不知何故随机链接顶点在一起（也许生成每个顶点一个随机数，那一定是边缘走出来的数表示顶点）。导线从任意一个顶点开始的图形（说与广度优先搜索），并让我们的随机图将所有的访问节点（这样一来，我们确保< codeG 连接）。

（2）生成一个随机方阵（ 0 的年代和 1 的）边长在 0 和 N （不知）。这将是邻接矩阵为图（对角矩阵应该再或者是所有的 1 的或全部 0 的）。使从图中的数据结构，并从任一节点遍历图形得到节点的连接列表，并调用图形。

任何其他的方式来产生足够随机图表示欢迎。 注意：我不需要一个纯粹的随机图，即生成图形不具有任何特殊的数学特性（如某种一致性）。我只是需要大量的图表和大量用于测试目的的东西。

下面是Java 节点我使用的类：

 公共类节点＆lt; T＆GT; {
    t个数据;
    ArrayList的＆LT;节点＆GT;孩子=新的ArrayList＆LT;节点＆GT;（）;
    ...}
 

下面是我使用了图类（你可以告诉我只是在一瞬间感兴趣的连通图为什么）：

 公共类图{
    节点mainNode;
    ArrayList的＆LT;节点＆GT; V =新的ArrayList＆LT;节点＆GT;（）;

    公共图形（节点节点）{
        mainNode =节点;
    }
    ...}
 

作为一个例子，我这​​是怎么做的图表用于测试目的现在：

  //下面做一个风筝图G（与A为主要节点）。
    / * A-B
           | / |
           光盘
    * /
    节点＆lt;字符串＆GT;一个新的=节点（一）;
    节点＆lt;字符串＆GT; B =新节点（B）;
    节点＆lt;字符串＆GT; C =新节点（C）;
    节点＆lt;字符串＆GT; D =新节点（D）;
    a.addChild（B）;
    a.addChild（C）;
    b.addChild（一）;
    b.addChild（C）;
    b.addChild（四）;
    c.addChild（一）;
    c.addChild（B）;
    c.addChild（四）;
    d.addChild（C）;
    d.addChild（B）;
    图G1 =新图（一）;
 

解决方案

不管你想要做你的图，我想它的密度也是一个重要的参数。否则，你只会产生一组采用随机尺寸小集团（完全图），然后将它们连接起来随机。

如果我是正确的，我建议你使用的鄂尔多斯 - 莱利模式：这很简单，从最初提出什么不远处，并允许您控制图密度（所以，基本上是：链接的数量）。

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

1. 定义的概率值p（越高p和图形的致密：0 =没有链接，1 =完全连通图）;
2. 创建您的n个节点（如对象，适合邻接矩阵，或任何你）;
3. 每对节点与一个（独立的）概率p连接。所以，你必须决定使用此概率为p它们之间的联系的存在。例如，我想你可以ranbdomly得出一个值Q 0和1之间，并创建链接IFF Q＆LT;页。然后做同样的事情，对每个可能的对节点图中的。

通过这种模式，如果p是足够大，那么它很有可能你的图是连通的（参见有关详细信息，维基百科参考）。在任何情况下，如果你有几个组件，您还可以通过创建不同的组件节点之间的联系迫使其连通性。首先，必须通过进行广度优先搜索（每个分量）来识别每个组件。然后，在两个不同的组件选择对节点，它们相互之间建立链接，并同时考虑组件合并。你重复这个过程，直到你有剩余的一个组成部分。

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:

(1) Generate a number between 0 and n and 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 G be all the visited nodes (this way, we make sure that G is connected).

(2) Generate a random square matrix (of 0's and 1's) with side length between 0 and 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.

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 Node class I am using:

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

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

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);

解决方案

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).

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.

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.

这篇关于如何生成随机图？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！