Алгоритм Крускала

Алгоритм Крускала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.

Алгоритм Крускала находит безопасное ребро для добавления в растущий лес путем поиска ребра (u, v) с минимальным весом среди всех ребер, соединяющих два дерева в лесу. Обозначим два дерева, соединяемые ребром (u, v), как С₁ и С₂. (u, v) — безопасное для С₁ ребро. Алгоритм Крускала является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимальн возможным весом.

Реализация алгоритма Крускала напоминает алгоритм для вычисления связных компонентов. Она использует структуру для представления непересекающихся множеств. Каждое множество содержит вершины дерева в текущем лесу. Операция Find_Set(u) возвращает представительный элемент множества, содержащего u. Таким образом, мы можем определить, принадлежат ли две вершины u и v одному и тому же дереву, проверяя равенство FindJSet(u) и Find_Set(v). Объединение деревьев выполняется при помощи процедуры Union.

Формальное описание     [вверх]

MST_Kruskal(G,w)
1    A «- пустое множество
2    for (Для) каждой вершины v є V[G]
3            do Make_Set(v)
4    Сортируем ребра из Е в неубывающем порядке их весов w
5    for (Для) каждого (u, v) G Е (в порядке возрастания веса)
6            do if Find_Set(u) != Find_Set(v)
7                     then A «- A объеденить с {(u, v)}
8                             Union(u, v)
9    return A

В строках 1-3 выполняется инициализация множества А пустым множеством и создается |V| деревьев, каждое из которых содержит по одной вершине. Ребра в Е в строке 4 сортируются согласно их весу в неубывающем порядке. Цикл for в строках 5-8 проверяет для каждого ребра (u, v), принадлежат ли его концы одному и тому же дереву. Если это так, то данное ребро не может быть добавлено к лесу без того, чтобы создать при этом цикл, поэтому в таком случае ребро отбрасывается. В противном случае, когда концы ребра принадлежат разным деревьям, в строке 7 ребро (и, у) добавляется в множество А, и вершины двух деревьев объединяются в строке 8.

Оценка сложности     [вверх]

Время работы алгоритма Крускала для графа G = (V, Е) зависит от реализации структуры данных для непересекающихся множеств. Будем считать, что лес непересекающихся множеств реализован с эвристиками объединения по рангу и сжатия пути, поскольку асимптотически это наиболее быстрая известная реализация. Инициализация множества А в строке 1 занимает время О (1), а время, необходимое для сортировки множества в строке 4, равно О (E*lgE) (стоимость |V| операций Make_Set в цикле for в строках 2-3 учитывается позже). Цикл for в строках 5-8 выполняет О (Е) операций Find_Set и Union над лесом непересекающихся множеств. Вместе с |V| операциями Make_Set эта работа требует времени О ((V + Е) * a(V)), где а — очень медленно растущая функция. Поскольку мы предполагаем, что G — связный граф, справедливо соотношение |E| >= |V| - 1, так что операции над непересекающимися множествами требуют О (Е *а(V)) времени. Кроме того, поскольку a(|V|) = О(lgV) = O(lgE), общее время работы алгоритма Крускала равно О (E*lgE). Заметим, что |Е| < |V|₂, поэтому lg |E| = О (lg V) и время работы алгоритма Крускала можно записать как О (Е * lg V).

Пример     [вверх ]

Выполнение алгоритма Крускала:

1. Начальная фаза. Минимальный покрывающий лес пуст.

2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.

3. Следующее безопасное ребро с весом 6. Добавляем его.

4-8. Добавляем остальные безопасные ребра.
                     

Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Визуализатор для алгоритма Крускала.

Ещё один пример выполнения алгоритма Крускаля. Заштрихованные ребра принадлежат растущему лесу.

[вверх]