Жадный алгоритм Краскала построения

Задача о минимальном остовном дереве

Эта задача довольно часто возникает на практике при строительстве линий электропередач, каналов связи, газопроводов и т.п.

Задача. Пусть имеется связный взвешенный граф. Веса можно истолковывать как стоимости, расстояния и т.д.

Требуется построить остов с минимальным суммарным весом. (Если граф не связный, то требуется построить минимальный лес).

Существует много способов нахождения какого-нибудь остова данного графа. Например, алгоритм поиска в глубину строит остов по ребрам возврата, но этот остов может не быть кратчайшим.

V₁ 1 V₂ V₁ 1 V₂

• • • •

4 2 2 2 2

• • • •

V₄ 1 V₃ V₄ V₃

Рис. 56. Граф Рис. 57. Дерево кратчайших путей

V₁ 1 V₂ V₁ 1 V₂

• • • •

2 2

• • • •

V₄ 1 V₃ V_{4 1} V₃

Рис. 58. Два кратчайших остова

кратчайшего остова

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

Замечание. Поиск наименьшего ребра существенно упрощается, если упорядочить длины ребер по возрастанию.

Дата добавления: 2014-01-06