MST. Алгоритмы Прима и Крускала

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?

Это минимальное остовное дерево не уникально

В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин (контактов), а E — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u,v) однозначно определено некоторое вещественное число w(u,v) — его вес (длина или стоимость соединения). w() называется весовой функцией.

Задача состоит в нахождении такого связного подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево T, у которого суммарный вес его ребер w(T) минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

Области применения

• Разработка сетей;
• Производство печатных плат;
• Наука, и в частности биология.

Построение минимального остовного дерева

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева.

Итак, пусть дан связный неориентированный граф G(V;E) c n вершинами и весовая функция w: E → R.

Искомый остов строится постепенно. Алгоритм использует некоторый подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u,v) выбирается так, чтобы оно было безопасным.

Безопасным ребром e относительно некоторой компоненты связности К из А называется ребро с минимальным весом, ровно один конец которого лежит в К.

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

Алгоритм Крускала объединяет вершины графа в несколько связных компонент, каждая из которых является деревом. На каждом шаге из всех ребер, соединяющих вершины из различных компонент связности, выбирается ребро с наименьшим весом. Необходимо проверить, что оно является безопасным: для этого в алгоритме Крускала все ребра графа G перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.

Собственно, сам алгоритм выглядит так:

1.	2.	3.	4.
5.	6.	7.	8.

Алгоритм Прима

Как и алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева.

Расcмотрим алгоритм:

1.	2.	3.	4.
5.	6.	7.	8.