Назад

Методы программирования

Задание 7. Построение остовного дерева (каркаса) графа минимальной стоимости

Общая информация

Задание состоит из двух частей, обе обязательны для выполнения. Необходимо реализовать два алгоритма построения каркаса графа минимальной стоимости: алгоритм Прима и алгоритм Краскала.

Теория

Рассмотрим некоторый связный неориентированный взвешенный граф. Каркасом, или остовным деревом для этого графа называется связный подграф этого графа, содержащий все вершины графа и не имеющий циклов. Количество ребер в каркасе связного графа всегда на единицу меньше количества вершин графа.

Ясно, что у графа может быть несколько каркасов. Например, различные каркасы можно построить, запуская поиск в глубину от разных вершин графа. Назовем стоимостью каркаса сумму весов ребер, входящих в него. На рисунке изображен граф и два его каркаса. Каркас стоимости 40 является минимальным.

Пример графа Каркас стоимости 44 Каркас стоимости 40

Алгоритм Прима (Prim)

Будем строить каркас графа следующим образом. Пометим все вершины графа, кроме одной (произвольной), как неиспользованные. Пока есть неиспользованные вершины, выбираем ребро наименьшего веса, соединяющее использованную вершину с неиспользованной, и добавляем его в каркас, делая эту неиспользованную вершину использованной.

Более формально алгоритм записывается следующим образом. Введем массив used[N], первоначально заполненный нулями. Пусть наш каркас первоначально пуст.

  1. Пометим первую вершину как использованную: used[0] = 1.
  2. Найдем ребро (i, j), соединяющее использованную вершину (used[i] == 1) с неиспользованной (used[j] == 0). Если таких ребер несколько, выберем ребро с минимальной стоимостью. Если таких ребер нет, закончим выполнение алгоритма.
  3. Добавим это ребро к каркасу.
  4. Пометим used[j] = 1.
  5. Перейдем к шагу 2.

Так как на каждом шаге алгоритма к каркасу добавляется новая вершина, в каркасе не будут появляться циклы. Каркас будет получаться минимальным, так как каждый раз выбирается ребро с минимальным весом из всех возможных (такие алгоритмы называют «жадными»).

Алгоритм Краскала (Kruskal)

В алгоритме Краскала мы не храним массив used[N]. Вместо этого мы будем на каждой итерации алгоритма проверять, принадлежат ли концы рассматриваемого ребра к разным компонентам связности (и добавлять ребро к каркасу, если это так).

Введем счетчик int counter = 0. Пусть N — количество вершин графа.

  1. Упорядочим список ребер по возрастанию веса.
  2. Если counter == N - 1, закончим выполнение алгоритма.
  3. Проходя по списку ребер, найдем ребро (i, j) такое, что i и j принадлежат разным компонентам связности. Так как список упорядочен по возрастанию веса ребер, мы будем выбирать ребро с минимальным весом, удовлетворяющее условию.
  4. Добавим это ребро в каркас, увеличим на единицу счетчик counter.
  5. Перейдем к шагу 2.

При реализации алгоритма можно использовать систему непересекающихся множеств для проверки того, входят ли две вершины в одну компоненту связности (изначально каждая вершина входит в своё множество, при добавлении ребра в каркас два соответствующих множества объединяются). Также для проверки связности двух вершин можно использовать любой известный алгоритм: поиск в ширину, поиск в глубину или что-либо другое.

Формулировка задания

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

Во входном файле input.txt задан неориентированный взвешенный граф в виде списка ребер. В файл output.txt выдать минимальный каркас этого графа в виде списка входящих в него ребер, используя алгоритм Прима.

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

Задание аналогично предыдущему. Использовать алгоритм Краскала.