11.2.4. Алгоритм построения максимальных независимых множеств вершин

Приведенный ниже алгоритм, обоснование которого дано в предыдущем разделе, строит все максимальные независимые множества вершин заданного графа.

Алгоритм 11.2. Построение максимальных независимых множеств

Вход: граф G(V, Е), заданный списками смежности Г[г>]

Выход: последовательность максимальных независимых множеств

k : - О { количество элементов в текущем независимом множестве }

S[k]: = 0 { S[k] — независимое множество из k вершин }

Q~ [k}: = 0 {Q~ [k] — множество вершин, использованных для расширения S[k] }

Q+ [fc]_: = V { Q⁺ [k] — множество вершин, которые можно использовать для расширения

S(k}}

Ml :{ шаг вперед }

select v e Q⁺ [k] { расширяющая вершина }

S[k + 1]: = S[k] U {v} { расширенное множество }

Q~[k + l}: = Q~ [k] \T[v] { вершина v использована для расширения }

<2⁺[fc+l]: ~Q⁺[k]\(T[v]U{v}) { все вершины, смежные с v, не могут быть использованы

для расширения }

М2 : { проверка } for и Е Q~ [k] do

if T[u]r\Q⁺[k] =0 then goto M3 { можно возвращаться }

end if end for if g+[fc] = 0 then

if Q~[k] = 0 then yield S[k] { множество S[k] максимально }

end if

goto M3 { можно возвращаться } else

goto Ml { можно идти вперед } end if

M3 : { шаг назад } v : = last(S[fc]) { последний добавленный элемент }

S[fc]: = S[k + 1] - {v}

Q~ [k]: = Q~ [k] U {v} { вершина v уже добавлялась }

Q⁺[k]: = Q+[k]\{v}

if fc = 0&<2+[fc] = 0 then

stop { перебор завершен } ebe

goto M2 { переход на проверку } end if

Пример

Известная задача о восьми ферзях (расставить на шахматной доске 8 ферзей так, чтобы они не били друг друга) является задачей об отыскании максимальных не­зависимых множеств. Действительно, достаточно представить доску в виде гра­фа с 64 вершинами (соответствующими клеткам доски), которые смежны, если клетки находятся на одной вертикали, горизонтали или диагонали.