Suitable ADT for Graphs

Question

What are the suitable data structures for graphs ?

I guess the answer varies on the type of graph?

in any case, any recommendations?

Answer 1

When the graph is sparse, a Map<Vertex, List<Vertex>> (1) will do. If it's dense, a 2D array may also be used (2).

See:

(1) http://en.wikipedia.org/wiki/Adjacency_list

(2) http://en.wikipedia.org/wiki/Adjacency_matrix

Answer 2

Two of the most common structures for storing graphs are adjacency lists and adjacency matrices. Which to use typically depends both on what you're planning to do with the graph (as one may provide more optimal manipulation/access times than the other for a given algorithm), and also on the sparseness or density of the graph (lists are more compact for sparse graphs, matrices have less relative overhead the denser the graph is).

Answer 3

Seeing as you want an abstract data type, I won't mention anything about implementation.

A graph G = <V, E> is a set of vertices V, and a set of edges E where each element in E is a tuple e = <v1, v2>, and v1 and v2 are in V.

The following may look like Java but I'm really thinking of any sufficiently expressive language:

interface Graph {
    Set getVertices();
    Set getEdges();
    void addVertex(Object v);
    void addEdge(Object v1, Object v2);
    void removeVrtex(Object v);
    void removeEdge(Object v1, Object v2);
}

I think this is the bare minimum. I haven't specified what is returned by getEdges; if the language has a native tuple type it would a set of those. In practice you would want to add extra methods such as:

int getDegree(Object v);
void contractEdge(Object v1, Object v2);
boolean isIsthmus(Object v1, Object v2);  /* does removal of this edge increase the number of components? */
int numComponents();
boolean isConnected();  /* return numComponents() <= 1 */
boolean isCycle(Set path);  /* path is a set of edges. */

etc.

Extending this to digraphs is left as an exercise :-).