В алгоритме Краскала используется жадный подход к решению задачи, т.е. в любой момент выполнения данных алгоритмов существует множество ребер E’, представляющее подмножество некоторого минимального остовного дерева графа G. На каждом шаге алгоритмов из оставшихся ребер выбирается "лучшее" ребро, обладающее определенными свойствами, и добавляется к формируемому каркасу максимального веса. Одним из важных свойств любого ребра, добавляемого к E’, является его безопасность, т.е. то, что обновленное множество ребер E’ будет продолжать представлять подмножество некоторого минимального остовного дерева.

3. Описание алгоритма Краскала

Алгоритм Краскала может строить дерево одновременно для нескольких компонент связности, которые в процессе решения объединяются в одно связанное дерево.

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

Алгоритм состоит из следующей последовательности действий:

1. Создается список ребер R, содержащий длину ребра, номер исходной вершины ребра (i), номер конечной вершины ребра (j), признак включения данного ребра в дерево.

2. Данный список упорядочивается в порядке возрастания длин ребер.

3. Просматривается список R и выбирается из него ребро с максимальной длиной, еще не включенное в результирующее дерево и не образующее цикла с уже построенными ребрами.

4. Если все вершины включены в дерево и количество ребер на единицу меньше количества вершин, то алгоритм свою работу закончил. В противном случае осуществляется возврат к пункту 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- короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.

4. Пример работы алгоритма Краскала

Рисунок 1. Начальный граф

Рисунок 2. Максимальное остовное дерево.

В алгоритме Краскала мы не храним массив used [N]. Вместо этого мы будем на каждой итерации алгоритма проверять, принадлежат ли концы рассматриваемого ребра к разным компонентам связности (и добавлять ребро к каркасу, если это так).

Введем счетчик int counter = 0. Пусть N - количество вершин графа.

Упорядочим список ребер по возрастанию веса.