Why doesn't the Bron-Kerbosh algorithm work?

Question

Python

I am developing an algorithm for finding an internal stable subset. I use the Bron-Kerbosh algorithm from Wikipedia

For some reason, for the graph that is presented in the code [[1,2],[1,4],[1,3],[2,4],[3,4],[4,5]], the algorithm returns such sets [5], [1,4], [1,4], which is naturally not correct. But it seems that I do everything according to the instructions I

changed the check function. She didn't work right. Now it returns adjacent vertices with item vertex. It uses the graph itself, which is represented in algebraic form.

But the result of the algorithm itself is still wrong

def check(item):
  temp = []
  for i in range(6):
    if item in graf[i]:
      if graf[i][0] not in temp:
        temp.append(graf[i][0])
      if graf[i][1] not in temp:
        temp.append(graf[i][1])

  return temp

def alg(s,add,exists):
    for item in add:
        s.append(item) # добавляем вершину item из множества add 
        new_add = [v for v in add if v not in check(item)] # формируем новое множество вершин удаляя из него всех соседей вершины item (функция check вовзращает всех соседей вершины item)
        new_exists = [v for v in exists if v not in check(item)] # тут тоже самое как для new_add
        if len(new_add) == 0 and len(new_exists) == 0:
            print(s)
            return s
        else:
            alg(s,new_add,new_exists)
        s.remove(item)
        add.remove(item)
        exists.append(item)

if __name__ == '__main__':
    graf = [[1,2],[1,4],[1,3],[2,4],[3,4],[4,5]]

    count_vershin = 5
    count_reber = 6

    # создание вложенного списка - двумерный массив
    matrix = [[0] * count_vershin for i in range(count_vershin)]

    # создание матрицы смежности
    for i in range(count_reber):
        k = graf[i-1][0]
        j = graf[i-1][1]
        # print(k,j)
        matrix[k-1][j-1] = 1
        matrix[j-1][k-1] = 1

    # вывод матрицы смежности
    for i in range(count_vershin):
        for j in range(count_vershin):
            print(matrix[i][j], end=' ')
        print()

    s = [] # множество, содержащее на каждом шаге рекурсии независимое множество для данного шага. Строится рекурсивно.
    add = [] # множество вершин, которые могут увеличить 
    exists = [] #  множество вершин, которые уже использовались для расширения  на предыдущих шагах алгоритма.

    for item in graf:
        if item[0] not in add:
            add.append(item[0])

        if item[1] not in add:
            add.append(item[1])


    print(add) # по сути тут у нас список исходных вершин
    print(alg(s, add, exists))

Answer 1

You have two big mistakes with the python language. You are iterating over the add list in a loop in alg, changing it. You can't do that. Iterators break and you miss half of the elements.
Instead, use a while loop:

while add:
  item = add[0]
  add.remove(item)
  s.append(item)
...

The second big mistake, in python, lists are passed by reference! So s, which is your recursive function parameter, is the same list at every level. But when you output a set, you immediately return from the function without removing item from s. You want all changes to s to be undone when their function exits. Do s.remove(item) before return.
These two changes should work. Well, your main optimization of the algorithm is not implemented either. It is necessary to check at the beginning of the loop that among the remaining vertices in add there is at least one connected to each vertex from exists. If there are none, you need to fall out of the loop.
More code:
range(n)in python it returns 0..5. You have a loop through the edges in __main__ and there is a call to i-1 in the graf array. Those. reference to [-1]. You probably didn't want it. Works by pure chance, because in python a[-1] gives the last element.
And in general, you are building an adjacency matrix, but you are not using it anywhere.
Instead of the check() function, you make a normal adjacency list once, otherwise it just hurts the eye from suboptimality.

neighbors = [[] for i in range(count_vershin)]
for edge in graf:
  neighbors[edge[0]-1].append(edge[1]-1)
  neighbors[edge[1]-1].append(edge[0]-1)