1

Given a graph G=(V, E), a subset S that belongs to V, and the subset S' containing every vertex of G not belonging to S, I want to count the total number of edges between the nodes of S and S'.

An algorithm that could solve this problem with better complexity than O(n^2).

4

1 回答 1

3

假设“低于 O(n^2)”你的意思是像 O(|E|)，那么你可以通过使用散列结构来做到这一点。将 S 的所有节点放入哈希集中，遍历 G 的所有边，并为每条边检查两个端点是否都在哈希集中。构建哈希集是 O(n)，假设一个合理的哈希函数，处理所有边是 O(|E|)。如果|E| in Omega(n^2)，你不能比 O(n^2) 做得更好。

编辑：两件事：

  • 最后一个关于如果错了就不能做得更好的陈述|E| in Omega(n^2)，取决于您用于图表的表示。令E' = {e = {s,v} in E | s in S}为与 S 中至少一条边相关的一组边。如果您有相关/邻接列表，那么您可以通过仅迭代与 S 中的节点相关的边来将复杂度提高到 O(|E'|)，和 |E'| 可能小于 |E| 由一个取决于 S 的非常数因子。
  • 该方法很容易转化为找到在 S 和 V\S 之间运行的边。只需创建两个哈希集，将 S 中的所有节点放入第一个，将 V\S 中的所有节点放入另一个。然后将条件调整为仅接受一个哈希集中的一个末端节点和另一个哈希集中的另一个末端节点的边。根据两个诱导子图的大小和密度，它应该只迭代与集合中具有较少边缘的节点相关的边缘。
于 2013-06-14T12:50:28.507 回答