c++ - 适合图中不断删除的最佳数据结构

Question

我正在用 C++ 构建一个图作为整数 vector 的 vector

vector<vector<int> > graph;

我的问题是:

• 图表是双向的，这意味着

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

• 我需要能够

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

  在恒定时间内。

这个删除是一个我会重复很多次的操作，所以单个映射不起作用，因为当我删除一个元素时，其他元素会返回一个索引。

我想删除一条边(例如，G[u] 的最后一个索引，因此我可以使用 pop_back 并获取 O(1) )，然后删除另一个顶点的邻接 vector 中的相应边(由于这不是我正在编写的算法的主要问题，并且该算法必须在线性时间内运行，因此我认为必须有一种方法使该操作保持不变)。

Answer 1

使用unordered_set ，基于哈希的集合，用于内部数据结构。

也就是说，而不是

vector<vector<int> > graph;

使用

vector<unordered_set<int>> graph;

查找从 u 到 v 是否存在边:

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

如果存在这样的边缘，则将其删除:

graph[u].erase(v);

所有这些操作预计O(1)。