What is the most efficient way to store a non-directed graph?

Question

As the title says.. What is the most efficient way to store a connected graph in java?

For example lets say I have multiple locations connecting to each other in various ways and I have to traverse through the graph to see if it's connected.. any help/comment would be helpful thanks!

Answer 1

One often used representation is a matrix (two dimensional array) indexed by all the nodes in the graph, where M[i,j] == true if there is a directed edge from node i to j. A variation on the theme is to store the length / weight of the edge between the two nodes (where a missing edge may be represented by the value -1).

Answer 2

use an adjacency matrix without the symmetry, thereby representing direction instead of simple adjacency.

Answer 3

Using an incidence or adjacency matrix will do the trick.

If you use an adjacency matrix, a sparse matrix might be efficient to use, if you have a lot of nodes. Colt provides a sparse matrix implementation. Info taken from this SO post.

Also, I've used JUNG sucessfully before, so you might want to take a peek under the hood to see how they've implemented directed graphs.

Answer 4

For lookup efficiency - use a boolean matrix (true if there is an arc connecting the nodes, false if there isn't). For memory efficiency define one of your object properties as a (dynamic) list of objects its pointing to. Note the latter will only help if you have a LOT of nodes in your graph.

Answer 5

Am I missing something? The data is already a graph, just serialize it.For the question as written talk of matrices is completely premature.