10. Алгоритмы нахождения минимального остовного дерева графа: алгоритм Прима, алгоритм Крускала Алгоритм Крускала

Здесь построение MST начинается с графа, состоящего только из n вершин графа G и не имеющего ребер. Таким образом, каждая вершина является связанной (сама с собой) компонентой. Это дает n связных компонент. В процессе выполнения алгоритма связанные компоненты постепенно объединяются друг с другом, формируя остовное дерево.

При построении постепенно возрастающих связанных компонент поочередно проверяются ребра из множества E в порядке возрастания их длин. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в остовное дерево. Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связанную компоненту может привести к образованию цикла. Число ребер, необходимое для остовного дерева равно n-1. Граф связан, а значит E содержит как минимум такое их количество. Когда остовное дерево будет содержать n-1 ребер, алгоритм завершается.

Создать список ребер L, в неубывающем по длине порядке

while число отмеченных ребер < n-1 do begin

Удалить w из головы списка L;

if w соединяет две несвязных компоненты then

отметить w и добавить к MST

else {w - внутри компоненты}

не отмечать w {это приведет к циклу в MST}

end;

Рисунок 18. Алгоритм Крускала

Сложность алгоритма для графа с n вершинами и m ребрами пропорциональна O(m*log m).