Задание состоит из двух частей, обе обязательны для выполнения. Необходимо реализовать два алгоритма построения каркаса графа минимальной стоимости: алгоритм Прима и алгоритм Краскала.
Рассмотрим некоторый связный неориентированный взвешенный граф. Каркасом, или остовным деревом для этого графа называется связный подграф этого графа, содержащий все вершины графа и не имеющий циклов. Количество ребер в каркасе связного графа всегда на единицу меньше количества вершин графа.
Ясно, что у графа может быть несколько каркасов. Например, различные каркасы можно
построить, запуская поиск в глубину от разных
вершин графа. Назовем стоимостью каркаса сумму весов ребер, входящих в него.
На рисунке изображен граф и два его каркаса. Каркас стоимости 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 выдать минимальный каркас
этого графа в виде списка входящих в него ребер, используя алгоритм Прима.
Задание аналогично предыдущему. Использовать алгоритм Краскала.