Vertex representation of a weighted unidirectional graph

Question

I am using adjacency matrix to represent all the vertex of my weighted unidirectional large graph. In this graph no edge connects a vertex to itself. This makes all the diagonal elements of my adjacency matrix null. As my graph is large so in adjacency matrix i need not to save any elements in left triangle. Below is a small sample graph with adjacency matrix.

In an unidirectional graph left triangle is just mirror image of right triangle. i.e. adjacency_matrix[i][j], adjacency_matrix[j][i] are same. so why to store the left triangle. for a large graph this trick can save so much memory. At the same time diagonal elements are also zero since no edge connects a vertex to itself. i.e. adjacency_matrix[i][i] are zero. But how can i implement this? can 2D array be used here?

Answer 1

Java doesn't really have 2D arrays, although there is syntatic sugar for allocating an array of arrays.

You probably just want:

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

That will allocate the triangle you want. Then just index row r, col c at weight[r][c-r-1].

The other option is just to use a single array with

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

The indexing can be a bit more complicated to compute, but less allocation and pointer overhead.