Алгоритм Крускала
Алгоритм Крускала — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые описан Джозефом Крускалом в 1956 году.
Алгоритм Крускала находит безопасное ребро для добавления в растущий лес путем поиска ребра (u, v) с минимальным весом среди всех ребер, соединяющих два дерева в лесу. Обозначим два дерева, соединяемые ребром (u, v), как С1 и С2. (u, v) — безопасное для С1 ребро. Алгоритм Крускала является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимальн возможным весом.
Реализация алгоритма Крускала напоминает алгоритм для вычисления связных компонентов. Она использует структуру для представления непересекающихся множеств. Каждое множество содержит вершины дерева в текущем лесу. Операция 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|2, поэтому lg |E| = О (lg V) и время работы алгоритма Крускала можно записать как О (Е * lg V).
Пример [вверх ]
Выполнение алгоритма Крускала:
1. Начальная фаза. Минимальный покрывающий лес пуст.
2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А.
3. Следующее безопасное ребро с весом 6. Добавляем его.
4-8. Добавляем остальные безопасные ребра.
Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.
Визуализатор для алгоритма Крускала
Ещё один пример выполнения алгоритма Крускаля. Заштрихованные ребра принадлежат растущему лесу.
Ещё один пример выполнения алгоритма Крускаля. Заштрихованные ребра принадлежат растущему лесу.
