3

Разрабатываю алгоритм нахождения внутреннего устойчевого подмножества. Использую алгоритм Брона-Кербоша из Википедии

Почему-то для графа, который представлен в коде [[1,2],[1,4],[1,3],[2,4],[3,4],[4,5]], алгоритм возвращает такие множества [5], [1,4], [1,4], что естественно не правильно. Но вроде все по инструкции делаю

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))

Я исправил функцию check. Она возвращала не понятно что. Теперь она возвращает смежные вершины с вершиной item.

Но результат самого алгоритма все равно неверный

2
  • 2
    Не забудьте добавить ответ ниже, если решите проблему самостоятельно раньше других =)
    – vp_arth
    8 ноя 2020 в 10:51
  • @vp_arth Выложил 8 ноя 2020 в 11:46

1 ответ 1

2

Вроде исправил, возвращает внутреннее устойчивые подмножества. Там есть закомментированные переменные graf, это я проверял для разных графов мой алгоритм

def check(item):
  temp = []
  for i in range(len(graf)):
    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)
        new_add = [v for v in add if v not in check(item)]
        new_exists = [v for v in exists if v not in check(item)]

        if len(new_add) == 0 and len(new_exists) == 0:
            print(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]]
    # graf = [[1,2],[1,5],[2,5],[2,3],[3,4],[4,5],[4,6]]
    graf = [[1,2],[1,4],[2,3],[3,5],[5,6],[5,4]]

    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])

    alg(s, add, exists)
    

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.