6.8.1. Жадный алгоритм построения минимального остовного дерева

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

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

Включение в строящееся остовное дерево выбранного ребра на очередном шаге жадного алгоритма выполняется слиянием двух компонент которым принадлежит по вершине нового ребра, и включением самого ребра в объединенное множество ребер. Процесс роста объединения компонент к остовному дереву продолжаем до тех пор, пока не будет включено ребро.

Справедливость жадного алгоритма является следствием следующих двух лемм.

• Лемма 6.8.1. Пусть связный неориентированный граф и произвольное остовное дерево для него. Тогда:

1) существует единственная между ними цепь в

2) если к добавить ребро из то возникнет ровно один цикл.

Доказательство. Утверждение 1 верно, в противном случае в существовал бы цикл, что противоречит дереву Утверждение 2 верно, поскольку между вершинами добавляемого ребра уже есть одна цепь, а значит, возникнет один цикл.

• Лемма 6.8.2. Пусть связный неориентированный граф, для каждого ребра и определен вес компоненты связности жадного алгоритма, объединение которых согласно алгоритму, растет к остовному дереву где Пусть следующим найденным для включения ребром является ребро наименьшего веса из оставшихся и пусть Тогда найдется остовное дерево для содержащее ребра вес которого не больше любого другого остовного дерева, содержащего ребра

Доказательство. Допустим противное. Пусть существует остовное дерево содержащее и не содержащее ребра вес которого меньше веса любого остовного дерева содержащего По утверждению 1 леммы 6.8.1, при добавлении образуется цикл. Этот цикл должен содержать такое ребро отличное от что цикл входит в по ребру то он должен и выйти из (рис. 6.19). Из условия следует, что вес , так как и ребро выбиралось с минимальным весом из оставшихся ребер без образования циклов, в противном же случае выбор должен был бы пасть на оно тоже не образует циклов с

Рис. 6.19

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

Реализация «жадной» схемы формирования остовного дерева представлена в алгоритме 6.7. Используемые при его описании обозначения соответствуют тому, что вводилось при обосновании жадной схемы. Вектор меток вершин графа поддерживает их принадлежность компонентам связности из которых формируется реберный список остовного дерева. Начальные величины устанавливаются равными порядковым номерам соответствующих вершин Далее значения корректируются по мере слияния компонент сохраняя соответствие принадлежности им вершин. Исходный граф задается реберным списком выходное остовное дерево также формируется реберным списком

Алгоритм 6.7. Жадный алгоритм минимального остовного дерева

(см. скан)

• Сложность жадного алгоритма. Жадный алгоритм требует предварительной сортировки ребер по их весам. Стандартные методы сортировки имеют сложность Сложность алгоритма 6.7 помимо сложности сортировки зависит от сложности реализации слияния подмножеств Сложность данной операции при полном переборе вершин данных подмножеств (как представлено в алгоритме 6.7) составляет Значит, сложность жадного алгоритма Программная реализация жадного алгоритма представлена в алгоритме 6.8, который близко соответствует множественному описанию соответствующего алгоритма 6.7.

Алгоритм 6.8. Программа жадного алгоритма

(см. скан)

(см. скан)

(см. скан)

Рассмотрим пример построения минимального остовного дерева графа, изображенного на рис. 6.20, по программе алгоритма 6.8.

Рис. 6. 20. Пример расчета остовного дерева

Для программы этого алгоритма исходные данные графа на рис. 6.20 задаются реберным списком в текстовом файле со следующей структурой:

• в первой строке файла содержится количество ребер в списке (12);

• во второй и третьей строках указываются ребра своими вершинами: одна вершина во второй строке, другая вершина ребра в третьей строке;

• в четвертой строке располагаются значения весов соответствующих ребер.

Результаты расчетов сохраняются в выходном файле со следующей структурой:

Обозначения данных в файле число ребер в графе; число вершин в графе; X — список вершин графа; сортированный список ребер графа; веса ребер согласно их сортировке; ребра остовного дерева; веса ребер остовного дерева; Вес — сумма весов ребер остовного дерева.