Алгоритм Краскала определения минимального остовного дерева

Для использования алгоритма Краскала применяется список ребер графа. Метод состоит в последовательном подключении к остовному дереву ребер с минимальным весом и заключается в следующем.

Предварительный этап. Список ребер сортируется в порядке возрастания весов. Ребро, имеющее минимальный вес (первое в упорядоченном списке), включается в искомый остов.

Этап, повторяющийся (N-1) раз (общий этап). Очередное ребро в списке включается в остов, если оно не образует цикл. Если ребро образует цикл с уже включенными в остов ребрами, то оно вычеркивается из списка и просматривается следующее по списку ребро.

Заключительный этап. Список включенных ребер составляет остов графа, а их суммарный вес определяет вес остовного дерева.

Рис. 1.

Пример

Известна стоимость обеспечения связи между источником и потребителями информации (рис. 2).

Рис. 2.

Нужно синтезировать топологию сети, обеспечивающей минимальную стоимость. Требуется определить методами Краскала и Прима минимальное остовное дерево графа G (5, 10), представленного на рис. 2.

Метод Прима. Матрица весов, получаемая после предварительного этапа алгоритма, представлена в табл. 1, где в качестве начальной выбрана вершина 3.

Задачей общего этапа является помечивание всех столбцов таблицы. В 3-й строке находится минимальный элемент w₃₄=2. 4-й столбец, содержащий минимальный элемент, помечается номером строки, где этот элемент находится. Элементу w₄₃ присваивается сколь угодно большое значение. В непомеченных столбцах 3-й и 4-й строк находится минимальный элемент w₃₂=3. 2-й столбец, его содержащий, помечается номером 3-й строки. Элементу w₂₃ присваивается сколь угодно большое значение. После этого шага матрица имеет вид, представленный в табл. 2.

В непомеченных столбцах 2, 3 и 4-й строк находится минимальный элемент w₂₅ =1. 5-й столбец помечается номером 2-й строки, где находится минимальный элемент. Элементу w₅₂ присваивается сколь угодно большое значение. На очередном шаге общего этапа в непомеченных столбцах 2, 3, 4 и 5-й строк находится минимальный элемент w₂₁=5. 1-й столбец помечается номером 2, элементу w₁₂ присваивается сколь угодно большое значение. Матрица после этого шага имеет вид, представленный в табл. 3.

Все столбцы таблицы помечены, общий этап закончен.

На заключительном этапе выписывается последовательность вершин, ребра между которыми включаются в минимальное остовное дерево. Это ребра, соединяющие вершины 1−2, 2−3, 3−4, 2−5.

Вес остовного дерева равен 5+3+2+1=11. Полученное остовное дерево показано на рис. 3.

Метод Краскала. По заданному графу (рис. 2) составляется список ребер (см. табл. 4), который на предварительном этапе упорядочивается в порядке возрастания весов (табл. 5). Ребро № 7, имеющее минимальный вес, включается в искомое остовное дерево (рис. 4). Выполняется общий этап. Второе по весу ребро № 6 также включается в остов. Следующее по весу ребро № 1 включается в остовное дерево, так как оно не образует цикла с ребрами № 6 и 7 (рис. 4). Ребро № 5 с минимальным весом среди оставшихся не включается в остов, так как оно образует цикл с ребрами № 1, 6 и 7. Следующее по весу ребро № 10 включается в остов. Вес остова равен 11, а его структура совпадает со структурой остова, полученного методом Прима (см. рис. 3).

Реализация алгоритма Краскала требует предварительной сортировки весов всех ребер. Алгоритм Прима не имеет этого недостатка.