Задание состоит из двух частей, обе обязательны для выполнения. Необходимо реализовать два алгоритма построения каркаса графа минимальной стоимости: алгоритм Прима и алгоритм Краскала.
Рассмотрим некоторый связный неориентированный взвешенный граф. Каркасом, или остовным деревом для этого графа называется связный подграф этого графа, содержащий все вершины графа и не имеющий циклов. Количество ребер в каркасе связного графа всегда на единицу меньше количества вершин графа.
Ясно, что у графа может быть несколько каркасов. Например, различные каркасы можно
построить, запуская поиск в глубину от разных
вершин графа. Назовем стоимостью каркаса сумму весов ребер, входящих в него.
На рисунке изображен граф и два его каркаса. Каркас стоимости 40
является
минимальным.
Будем строить каркас графа следующим образом. Пометим все вершины графа, кроме одной (произвольной), как неиспользованные. Пока есть неиспользованные вершины, выбираем ребро наименьшего веса, соединяющее использованную вершину с неиспользованной, и добавляем его в каркас, делая эту неиспользованную вершину использованной.
Более формально алгоритм записывается следующим образом. Введем массив used[N]
,
первоначально заполненный нулями. Пусть наш каркас первоначально пуст.
used[0] = 1
.(i, j)
, соединяющее использованную вершину
(used[i] == 1
)
с неиспользованной (used[j] == 0
). Если таких ребер
несколько, выберем ребро с минимальной стоимостью. Если таких ребер
нет, закончим выполнение алгоритма.used[j] = 1
.Так как на каждом шаге алгоритма к каркасу добавляется новая вершина, в каркасе не будут появляться циклы. Каркас будет получаться минимальным, так как каждый раз выбирается ребро с минимальным весом из всех возможных (такие алгоритмы называют «жадными»).
В алгоритме Краскала мы не храним массив used[N]
. Вместо этого мы будем
на каждой итерации алгоритма проверять, принадлежат ли концы рассматриваемого ребра
к разным компонентам связности (и добавлять ребро к каркасу, если это так).
Введем счетчик int counter = 0
. Пусть N
— количество вершин графа.
counter == N - 1
, закончим выполнение алгоритма.(i, j)
такое, что
i
и j
принадлежат разным компонентам
связности. Так как список упорядочен по возрастанию веса ребер,
мы будем выбирать ребро с минимальным весом, удовлетворяющее условию.counter
.При реализации алгоритма можно использовать систему непересекающихся множеств для проверки того, входят ли две вершины в одну компоненту связности (изначально каждая вершина входит в своё множество, при добавлении ребра в каркас два соответствующих множества объединяются). Также для проверки связности двух вершин можно использовать любой известный алгоритм: поиск в ширину, поиск в глубину или что-либо другое.
Во входном файле input.txt
задан неориентированный взвешенный граф
в виде списка ребер. В файл output.txt
выдать минимальный каркас
этого графа в виде списка входящих в него ребер, используя алгоритм Прима.
Задание аналогично предыдущему. Использовать алгоритм Краскала.