如何生成随机图？

Question

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

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

(2)生成一个边长在(和某种程度上)之间的随机方阵(0's和1's ).这将是我们图形的邻接矩阵(矩阵的对角线应该是全部或全部的).从图形中创建数据结构并从任何节点遍历图形以获得连接的节点列表并调用该图形.0n10G

任何其他生成足够随机图的方法都受到欢迎.注意:我不需要纯随机图,即,您生成的图不必具有任何特殊的数学属性(如某种统一性).我只需要大量的图表来测试其他东西.

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

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

这是Graph我正在使用的类(你可以告诉我为什么我现在只对连接图感兴趣):

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

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

例如,这就是我现在为测试目的制作图表的方法:

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

Answer 1

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

如果我是正确的,我会建议你使用Erdős-Rényi模型:它很简单,与你最初提出的模型相差不远,并允许你控制图形密度(所以,基本上:链接的数量).

以下是此型号的简短说明:

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

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