生成随机对称加权邻接矩阵

我试图通过使用成本邻接矩阵来测试Prim's和Kruskal算法的实现。我将根据图中顶点的数量以及图中边的数量生成这些矩阵。它不必是一个连通图。生成随机对称加权邻接矩阵

这是我到目前为止有：

final static int infinity = 2000000000; 
public static int[][] genAdjMat(int V, int E) { 
    int[][] a = new int[V][V]; 
    int e = E; 

    for(int i = 0; i < V; i++) { 
     for(int j = i; j < V; j++) { 
      if(i == j) { 
       a[i][j] = 0; 
      } 
      else { 
       if(Math.random() < 0.5 && e >= 0) { 
        int temp = (int)Math.ceil(Math.random()*e); 
        a[i][j] = temp; 
        a[j][i] = temp; 
        e--;   
       } 
       else { 
        a[i][j] = infinity; 
        a[j][i] = infinity; 
       } 
      } 
     } 
    } 
    return a; 
}

眼下，它会产生一个对称的数组，但它不使用我指定的所有边缘。我很难弄清楚如何使用所有边缘，并且仍然让它们随机放置在整个矩阵中，同时保持对称性。

来源

2016-12-02 Ben Jamink

做相反的事情。初始化一个空矩阵并添加'E'个随机边。 –

哇，我觉得很愚蠢。这很简单，谢谢给我另一种方式来做到这一点！ –

我建议如下：

生成所有可能的无向边（V * (V - 1)/2项目）的名单。
随机播放它。
挑选第一个E边缘。

来源

2016-12-02 20:29:20 kraskevich

这是一个很好的解决方法！我最终选择了一个修改后的版本，在那里我先用随机加权边填充图形，然后放入边缘错过的无穷大！ –

直向前方：只是独立生成边缘。

Random random = new Random(); 
Set<Map.Entry<Integer,Integer>> edges = Sets.newHashSet(); 
for (int i=0; i<e; i++) { 
    do { 
     int xCoordinate = random.nextInt(V); 
     int yCoordinate = random.nextInt(V); 
    } while(!edges.add(xCoordinate, yCoordinate)); 
}

现在使用边缘将它们放入矩阵中。

或者（在迭代矩阵时），使用以下概率函数：p(A[i,j] == 1) = (e - k)/(V^2 - (i * V + j))。其中k是已分配边的数量。这一点是 - 有一个概率小于1，而剩余条目的数量仍然高于你必须分配的边数，当你仍然需要分配的边数等于剩余的数时，这将变为1要迭代的条目。

来源

2016-12-02 20:46:10

生成随机对称加权邻接矩阵

回答

相关问题