ランダム対称ウェイト付き隣接行列を生成する

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エッジを選択します。

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になります繰り返し処理するエントリ。