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 is empty 会发生什么。由于 u 是未定义的，函数是以 N(u) 作为空集继续执行(即它继续处理 P 中的每个顶点 v)，还是返回给调用者？

Answer 1

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

if P and X are both empty:

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

换句话说:如果 P 并集 X 为空，我们将 R 报告为最大团。