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!
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).
use an adjacency matrix without the symmetry, thereby representing direction instead of simple adjacency.
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.
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.
Am I missing something? The data is already a graph, just serialize it.For the question as written talk of matrices is completely premature.
