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
Printable View
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
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.
My mothod is the same as yours at present :(Quote:
Originally Posted by harsh4u8
Implement it as a list. If you maintain an Adjacency Matrix, you can never get rid of the redundant entries.