algorithm - 用于集团查找的 Bron Kerbosh 算法 - 当枢轴顶点不存在时会发生什么？

Question

BK clique 的维基百科伪代码通过旋转找到：

   BronKerbosch2(R,P,X):
   if P and X are both empty:
       report R as a maximal clique
   choose a pivot vertex u in P ⋃ X
   for each vertex v in P \ N(u):
       BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

我不清楚 P union X 是空的会发生什么。由于 u 是未定义的，函数是否继续以 N(u) 作为空集（即它继续为 P 中的每个顶点 v），还是返回给调用者？

Answer 1

当且仅当 P 和 X 都为空时，P union X 为空。此条件在行中检查

if P and X are both empty:

因此，如果此条件失败，则意味着 P 或 X 或两者都不为空。因此，P union X 中必须至少有一个元素。

换句话说：如果 P union X 为空，我们report R as a maximal clique.

Answer 2

我们为 的值选择什么并不重要u。你的假设是P union X空的，这意味着两者P都是X空的。因此，让我们暂时忽略 的值u并转到下一行“ for each vertex v in P \ N(u):”。既然P是空的，那么P \ N(u)仍然是空的。所以无论如何都会跳过for循环。因此，如果它让您感觉更好，您可以在其中放置一个 return 语句，但正如它目前所写的那样，它仍然会停止算法的执行。