Graph in c++

ive always wondered why dont we use unordered maps instead of vector while implementing.
It will be better in terms of space as well as time, is what i think .
can anyone pls shed some light on this topic.
thanks

There are some frequent operations that will not be able to perform without a vector like
Store duplicate values (unless you are planning to use a multimap )

Alo the main reason
std::unordered_map (hash table) operations are amortized O(1) and worst case O(n)

How this plays out in practice is that the hash table “hiccups” every once in a while with an O(n)

and “Everybody Loves Vectors” :upside_down_face:

1 Like

everyone loves vector is more convincing :crazy_face: :stuck_out_tongue:

1 Like

It really depends on your use-case. In a typical graph algorithm, like DFS or BFS, you want to visit all neighbors. For that a vector of neighbors is perfect. You can’t be more efficient than that (both in space and in time). Using an unordered map to store all outgoing edges will take more space (because a hash-table needs to have empty entries to avoid frequent hash collisions). Time might be exactly the same, although it depends on the implementation of unordered_set. But it certainly will not be faster.

If you have a different use-case, then an unordered map might be better. E.g. if you are at a node, and you want to know if there is an edge to another node, the unordered map can answer such queries much faster than a vector.

2 Likes