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

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

我建议如下:

1. 生成所有可能的无向边的列表(V * (V - 1)/2 项)。

2. 随机播放。

3. 选择第一个 E 条边。