用于找出诱导子图是否完整的快速算法

Question

我有一个无向无加权图G =(V,E)和一个随机选择的顶点子集S. 我想检查S中的顶点是否相互邻接(即形成一个完整的子图/一个集团).

我有以下算法(伪代码):

foreach vertex in S  {
  // Check that the vertex has enough edges
  if (vertex.edges.count < S.size - 1)
    return false;

  // Check that there is an edge to each vertex in S
  foreach vertex2 in S  {
    if (!vertex.hasEdgeTo(vertex2))
      return false;
  }
}
return true;

问题是该算法的最坏情况性能是O(| V | ²)(在子集S包含完整图的所有顶点的情况下).

我的问题是:是否有更快的算法运行,具有更好的大O最坏情况复杂度？

Answer 1

假设您可以检查两个顶点是否重合于，则您的算法在最坏情况下O(1)具有时间复杂度。O(|V|\xc2\xb2) = O(|E|)我认为你不能做得比 更好O(|E|)，因为你应该真正检查子图的所有边缘。

\n