You can look at adjacency lists as a way of compressing the rows of the adjacency matrix. So you can choose instead to compress the columns into lists. This is a reverse adjacency list. You can also compress both dimensions by storing <row,col> -> value mappings in a map (hash table, tree, etc.)
There are other variations on adjacency lists. The "outer" list can be a linked list (single or double), array, or map from node id to list of adjacent nodes. Same for the "inner" list, but add the possiblity of maps where the key is the label on the edge. Several graph data structures are used for computational geometry: winged edge, half-edge, quad-edge, and vertex lists, for example. These support certain query and edit operations in constant time regardless of vertex degree. The best choice depends on the operations that must be performed and their relative frequency. In this choice you are often trading constant factors of memory usage for speed. On May 31, 2:06 pm, Mad Coder <imamadco...@gmail.com> wrote: > @Gene: Can you tell some other ways of graph representation in case of > sparse matrix as till now I consider adjacency list as the best method for > the same. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
