我希望能够在
Java中生成随机,无向和连接的图形.另外,我希望能够控制图中的最大顶点数.我不确定解决这个问题的最佳方法是什么,但这里有一些我能想到的:
(1)生成一个介于0和n之间的数字,并将其作为顶点数.然后,以某种方式将顶点随机链接在一起(可能每个顶点生成一个随机数,并将其作为从所述顶点出来的边数).从任意顶点开始遍历图形(比如使用广度优先搜索),让随机图G成为所有访问节点(这样,我们确保G连接).
(2)生成一个随机方阵(0和1),边长在0到n之间(不知何故).这将是我们图形的邻接矩阵(矩阵的对角线应该是全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).
/* a-b
|/|
c-d
*/
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);