C++ Graph implementation as a data structure

Hello, what is the best implementation of a Graph as a data structure in C++?
Thank you

Thereâ€™s no single â€śbestâ€ť implementation.

How would you represent edges? As an adjacency matrix or adjacency list (or possibly something else)? The former is better for dense graphs, the latter for sparse graphs; you canâ€™t just use both without worsening your worst-case complexity.

If your graph is weighted, you need to account for weights (edge/vertex, thatâ€™s one more fork); if itâ€™s not, you can save on time/space by using a â€śdifferentâ€ť data structure.

Trees are special. Cacti are special.

What about directed graphs? Some algorithms donâ€™t exist on undirected graphs (e.g. strongly connected components), some donâ€™t exist, or lose their meaning, on directed ones (e.g. connected components and Union-Find).

There are many graph algorithms which could hardly be mixed into one data structure (sure, you could work around it somehow, but itâ€™s not worth the effort).

A trie is a graph - a prefix tree. Shit gets real with Aho-Corasick (combining KMP and trie), and it gets complex with suffix trees.

Finally, one last piece of demotivation: most of the time, is it really necessary to make graphs DS? If youâ€™re in a timed contest, canâ€™t copy-paste and need to write a single graph algorithm used on a single graph (and thatâ€™s usually the case), why make it more complicated?

Okay, enough negativity. Itâ€™s sometimes worth it to implement some specific graphs with specific operations as data structures. Specifically, if you need to answer queries non-trivially, like with interval trees or some applications of HLD (in that case, whatâ€™s important isnâ€™t really the graph, but the extra functionality, and the graph is just a skeleton on which itâ€™s constructed).

Most of the time, all you need is an adjacency list as a 2D array in the main function. Adjacency matrix, sometimes.

2 Likes
//