java - 加权单向图的顶点表示

Question

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

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

Answer 1

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

您可能只想:

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

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

另一个选项是仅使用单个数组

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

索引的计算可能有点复杂，但分配和指针开销较少。