Adjacency Matrix Representation

[harsh4u8]

In an adjacency matrix for an undirected graph ,almost half the storage space required by the graph is unnecessary (the have 0 value).
please suggest a modification that uses less space

Regards
Harsh Jain

[nuzzle]

You mean that the array in principle consists of two triangles, one above the diagonal and one below the diagonal, and that they essentially hold the same information?

Then you can organize the matrix as an array of arrays. If the inner-most arrays have different lengths this is called a jagged matrix. In your case the inner-most arrays will have increasing lengths starting at 1, like

*
* *
* * *
* * * *

etcetera.

Just make sure the first index is bigger than the second when you access it, otherwise you need to swap them first.

[Boombaby]

In an adjacency matrix for an undirected graph ,almost half the storage space required by the graph is unnecessary (the have 0 value).
please suggest a modification that uses less space

Regards
Harsh Jain

My mothod is the same as yours at present

[shamim_h]

Implement it as a list. If you maintain an Adjacency Matrix, you can never get rid of the redundant entries.