Алгоритм Брон Кербоша для поиска клики - что происходит, когда вершины опоры не существует?

Question

Псевдокод из Википедии о нахождении клики БК с поворотом:

   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) в качестве пустого множества (то есть продолжается для каждой вершины v в P) или возвращает вызывающей стороне?

Answer 1

P union X пусто тогда и только тогда, когда P и 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) все равно будет пустым.Так что цикл будет пропущен несмотря ни на что.Поэтому, если вам станет лучше, вы можете поместить туда оператор return, но, как написано в данный момент, он все равно остановит выполнение алгоритма.