0

我正在使用邻接矩阵来表示我的加权单向大图的所有顶点。在该图中，没有边将顶点连接到自身。这使得我的邻接矩阵的所有对角元素null。由于我的图很大，所以在邻接矩阵中我不需要在左三角形中保存任何元素。下面是一个带有邻接矩阵的小样本图。这是具有邻接矩阵的示例小图

在单向图中，左三角形只是右三角形的镜像。即adjacency_matrix[i][j]，adjacency_matrix[j][i]相同。那么为什么要存储左三角形。对于大图，这个技巧可以节省很多内存。同时，对角元素也为零，因为没有边将顶点连接到自身。即adjacency_matrix[i][i]为零。但是我该如何实现呢？这里可以使用二维数组吗？

4

2 回答 2

3

Java 并没有真正的二维数组，尽管有用于分配数组数组的语法糖。

你可能只想：

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

这将分配你想要的三角形。然后只需在 weight[r][cr-1] 处索引行 r，col c。

另一种选择只是使用单个数组

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 回答