0

隣接行列を使用して、重み付けされた単方向の大きなグラフのすべての頂点を表しています。このグラフでは、頂点をそれ自体に接続するエッジはありません。これにより、隣接行列のすべての対角要素が作成されますnull。私のグラフは大きいので、隣接行列では左三角形の要素を保存する必要はありません。以下は、隣接行列を含む小さなサンプル グラフです。これは、隣接行列を含むサンプルの小さなグラフです

一方向グラフでは、左三角形は右三角形の鏡像です。すなわちadjacency_matrix[i][j]、adjacency_matrix[j][i]同じです。では、なぜ左三角形を保存するのでしょうか。大きなグラフの場合、このトリックは非常に多くのメモリを節約できます。同時に、頂点をそれ自体に接続するエッジがないため、対角要素もゼロになります。すなわちadjacency_matrix[i][i]、ゼロです。しかし、どうすればこれを実装できますか? ここで 2D 配列を使用できますか?

4

2 に答える 2

3

Java には実際には 2D 配列はありませんが、配列の配列を割り当てるためのシンタックス シュガーがあります。

あなたはおそらくただ欲しい：

int[][] weight = new int[N][];
for (int i = 0; i < N; i++) weight[i] = new int[N-1-i];

これにより、必要な三角形が割り当てられます。次に、行r、列cを重み[r] [cr-1]でインデックス付けします。

もう1つのオプションは、単一の配列を使用することです

int[] weight = new int[N*(N-1)/2];

インデックス作成は計算が少し複雑になる可能性がありますが、割り当てとポインターのオーバーヘッドは少なくなります。

于 2012-04-07T07:50:25.290 に答える
1

ジャグ配列を使用できます。

int[][] matrix = new int[N][];
for (int i = 1; i <= N; i++) {
   matrix[i] = new int[N - i + 1];
   for (int j = 1; j <= N - i + 1; j++)
       matrix[i][j] = edgeValue;
}

基本的に、各行に必要なだけ割り当てます。

PS たぶん、ここでいくつかの境界を台無しにしましたが、それでも要点を理解する必要があります:)

于 2012-04-07T07:49:30.057 に答える