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

Question

我正在尝试使用成本邻接矩阵来测试 Prim 和 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;
}

现在，它生成了一个对称数组，但它没有使用我指定的所有边。我无法弄清楚如何用完所有边并仍然将它们随机放置在整个矩阵中同时保持对称性。

Answer 1

我建议如下：

生成所有可能的无向边列表（V * (V - 1) / 2 项）。
随机播放。
选取前 E 条边。

Answer 2

直截了当：只需独立生成边缘。

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要迭代的条目。

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

Generate Random Symmetric Weighted Adjacency Matrix

java

algorithm

matrix

adjacency-matrix