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 перебираются по возрастанию веса. Для очередного ребра проверяется, не лежат ли концы ребра в разных компонентах связности, и если это так, ребро добавляется, и компоненты объединяются.
Собственно, сам алгоритм выглядит так:
- Сортируем ребра графа по возрастанию весов
- Полагаем, что каждая вершина относится к своей компоненте связности
- Проходим ребра в «отсортированном» порядке. Для каждого ребра выполняем:
- Если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву
- Если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения
- Если есть еще нерассмотренные ребра и не все компоненты связности объеденены в одну, то переходим к шагу 3, иначе выход.
Алгоритм Прима
Как и алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева.
Расcмотрим алгоритм:
- Множество остовных вершин — исходная вершина
- Множество оставшихся — все вершины за исключением исходной
- Пока множество оставшихся не пусто:
- Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.
- Для найденного ребра, вершину принадлежащую множеству оставшихся:
- Вычеркиваем из множества оставшихся.
- Добавляем к множеству остовных.