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