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. Проходим ребра в «отсортированном» порядке. Для каждого ребра выполняем:
    1. Если вершины, соединяемые данным ребром лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву
    2. Если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения
  4. Если есть еще нерассмотренные ребра и не все компоненты связности объеденены в одну, то переходим к шагу 3, иначе выход.

1. Начальная фаза. Минимальный покрывающий лес пуст

1.

2. Перебираем ребра в порядке возрастания веса: первое ребро с весом 2. Добавляем его к А

2.

3. Следующее безопасное ребро с весом 6. Добавляем его

3.

4.

4.

5.

5.

6.

6.

7.

7.

8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено

8.

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

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

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

  1. Множество остовных вершин — исходная вершина
  2. Множество оставшихся — все вершины за исключением исходной
  3. Пока множество оставшихся не пусто:
    1. Ищем ребро соединяющее множество остовных и множество оставшихся и имеющее наименьший вес.
    2. Для найденного ребра, вершину принадлежащую множеству оставшихся:
      • Вычеркиваем из множества оставшихся.
      • Добавляем к множеству остовных.

1. Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер

1.

2. Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову

2.

3. Следующее безопасное ребро с весом 11. Добавляем его

3.

4.

4.

5.

5.

6.

6.

7.

7.

8. Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено

8.


Оставить комментарий