Daniel Daniel - 3 months ago 7
C++ Question

best data structure to fit constant deletion in graph

I'm building a graph in c++ as a vector of integer vectors

vector<vector<int> > graph;


my problem is:


  • the graph is bidirectional, that means

    if G[u] contains v, G[v] contains u

  • I need to be able to

    remove any element v from G[u]
    remove u from G[v]


    in constant time.



And this removal is an operation I'm gonna be repeating a lot, so a single map won't work, cause when I remove an element, the other elements would come one index back.

I'd like to remove an edge (the last index of G[u], for example, so I could use pop_back and get O(1) ), and then remove the corresponding edge in the other vertex' adjacence vector (and as this is not the main problem of the algorithm I'm writing and it the algorithm must run in linear time, I think there must be a way to make this operations constant).

Answer

Use unordered_set, the hash-based set, for the internal data structure.

That is, instead of

vector<vector<int> > graph;

use

vector<unordered_set<int>> graph;

To find if there is an edge from u to v:

graph[u].find(v) != graph[u].end();

If there is such an edge, then to remove it:

graph[u].erase(v);

All these operations are expected O(1).