The GiG The GiG - 2 months ago 41
C++ Question

Graph implementation C++

I was wondering about a quick to write implementation of a graph in c++. I need the data structure to be easy to manipulate and use graph algorithms(such as BFS,DFS, Kruskal, Dijkstra...).
I need this implementation for an algorithms Olympiad, so the easier to write the data structure the better.

Can you suggest such DS(main structs or classes and what will be in them). I know that an Adjacency list and Adjacency matrix are the main possibilities, but I mean a more detailed code sample.

For example I thought about this DS last time I had to implement a graph for DFS:

struct Edge {
int start;
int end;
struct Edge* nextEdge;

and then used a array of size n containing in its i'th place the Edge List(struct Edge) representing the edges starting in the i'th node.

but when trying to DFS on this graph I had to write a 50 line code with about 10 while loops.

What 'good' implementations are there?


It really depends on what algorithms you need to implement, there is no silver bullet (and that's shouldn't be a surprise... the general rule about programming is that there's no general rule ;-) ).

I often end up representing directed multigraphs using node/edge structures with pointers... more specifically:

struct Node
    ... payload ...
    Link *first_in, *last_in, *first_out, *last_out;

struct Link
    ... payload ...
    Node *from, *to;
    Link *prev_same_from, *next_same_from,
         *prev_same_to, *next_same_to;

In other words each node has a doubly-linked list of incoming links and a doubly-linked list of outgoing links. Each link knows from and to nodes and is at the same time in two different doubly-linked lists: the list of all links coming out from the same from node and the list of all links arriving at the same to node.

It's a lot of pointer twiddling (so unless you love pointers just forget about this) but query and update operations are efficient; for example adding a node or a link is O(1), removing a link is O(1) and removing a node x is O(deg(x)).

Of course depending on the problem, payload size, graph size, graph density this approach can be way overkilling or too much demanding for memory (in addition to payload you've 4 pointers per node and 6 pointers per link).