Generate Random Symmetric Weighted Adjacency Matrix

Question

I'm trying to test implementations of Prim's and Kruskal's algorithm by using a cost adjacency matrix. I'm generating these matrices on the amount of vertices in the graph, and the amount of edges in the graph. It does not have to be a connected graph.

Here's what I have so far:

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;
}

Right now, it generates a symmetric array but it doesn't use all the edges that I specify. I'm having trouble figuring out how to use up all the edges and still have them randomly placed throughout the matrix while maintaining symmetry.

Answer 1

I'd suggest the following:

1. Generate the list of all possible undirected edges (V * (V - 1) / 2 items).

2. Shuffle it.

3. Pick the first E edges.