3.2 Алгоритм Краскала
Алгоритм Краскала— алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году. Вначале текущее множество рёбер устанавливается пустым. Затем, пока это возможно, проводится следующая операция: из всех рёбер, добавление которых к уже имеющемуся множеству не вызовет появление в нём цикла, выбирается ребро минимального веса и добавляется к уже имеющемуся множеству. Когда таких рёбер больше нет, алгоритм завершён. Подграф данного графа, содержащий все его вершины и найденное множество рёбер, является его остовным деревом минимального веса.
Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево. Полный граф задается списком ребер. Перед работой список ребер сортируется по возрастанию длины. На каждом шаге просматривается список ребер, начиная с ребра, следующего за вошедшим в решение на предыдущем шаге, и к строящемуся поддереву присоединяют то ребро, которое не образует цикла с ребрами, уже включенными в решение. Алгоритм состоит из следующей последовательности действий:
Создается список ребер R, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево. Данный список упорядочивается в порядке возрастания длин ребер. Просматривается список R и выбирается из него ребро с максимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами. Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.
Или в терминах теории графов:
Дан граф с n вершинами; длины ребер заданы матрицей. Найти остовное дерево максимальной длины. В задаче Прима-Краскала, которая не кажется особенно простой, жадный алгоритм дает точное оптимальное решение. Как известно (это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными. А как следить, чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет. Докажем, что описанный алгоритм получает в точности максимальное решение. Для доказательства нам понадобится очень простое утверждение: Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро. Действительно, пусть добавлено ребро (u, v) - “добавлено” означает, что ребро - новое, что раньше его в дереве не было. Поскольку дерево является связанным графом, то существует цепь C (u, …, v) из нескольких ребер, соединяющая вершины u и v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл.
Теорема. Алгоритм Прима-Краскала получает максимальное остовное дерево.
Доказательство.
Результатом работы алгоритма является
набор из n-1 ребер. Они не образуют цикла,
ибо на каждом из n-1 шагов соединялись
вершины разного цвета, т.е. ранее не
связанные. Этот граф связный, потому
что после проведения 1-го ребра осталось
n-1 разных цветов, …, после проведения
(n-1) - го ребра остался один цвет, т.е. одна
компонента связности. Итак, полученный
набор ребер образует связный граф без
циклов, содержащий n-1 ребер и n вершин.
Следовательно, граф есть остовное
дерево. Осталось доказать, что оно имеет
минимальную длину. Пусть {
, 
,
…, 
}
ребра остовного дерева в том порядке
как их выбирал алгоритм, т.е. 
≥
.
Предположим для простоты доказательства,
что все ребра сети имеют разную длину,
т.е.
> >…> (1)
Если
полученное дерево не максимально, то
существует другое дерево, заданное
набором из n-1 ребер {
, 
,
…, 
},
такое что сумма длин 
больше
суммы длин
.
С точностью до обозначений
> >…> (2)
Может
быть
=
,
=
и
т.д., но так как деревья разные, то в
последовательностях (1) и (2) найдется
место, где ребра отличаются. Пусть самое
левое такое место - k, так, что 
№
.
Поскольку
выбиралось
по алгоритму самым большим из не
образующих цикла с ребрами
,
,
…, 
,
то
>
.
Теперь добавим к дереву (2) ребро
.
В нем появится цикл, содержащий ребро
и,
может быть, какие-то (или все) ребра
,
,
…,
,
но они сами не образуют цикла, поэтому
в цикле будет обязательно ребро d из
набора
,
…,
,
причем d>
.
Выбросим из полученного графа с одним
циклом ребро d. Мы снова получим дерево,
но оно будет на d-
короче
минимального, что невозможно. Полученное
противоречие доказывает теорему для
сети со всеми разными ребрами.
Алгоритм состоит из следующей последовательности действий:
Создается список ребер E, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево.
Данный список упорядочивается в порядке возрастания длин ребер.
Просматривается список E и выбирается из него ребро с максимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.
Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 3.