Остовное дерево наименьшего веса и алгоритм Краскала

Следующая задача известна в теории графов под названием задачи Штейнера : на плоскости заданы точек; нужно соединить их отрезками прямых таким образом, чтобы суммарная длина отрезков была наименьшей.

В процессе поиска решения разрешено вводить новые точки; "длина" отрезка, соединяющего две заданные точки, не обязательно понимается буквально геометрически — это может быть некоторая количественная оценка "цены" прохождения из точки в точку по какой-то ломаной линии.

Можно дать следующую графовую интерпретацию задачи Штейнера. Дан неориентированный граф без ребер. Требуется найти неориентированный граф со специальными свойствами.

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

Требование, чтобы искомый граф

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

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

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

Неориентированный (ориентированный) граф, у которого каждому ребру (дуге) сопоставлено некоторое действительное число, называют взвешенным или размеченным графом. Это число называют весом или меткой ребра (дуги). Как правило, мы рассматриваем граф с натуральными метками ребер (дуг).

Алгоритм Краскала вычисляет для заданного взвешенного неориентированного графа остовное дерево наименьшего веса . Существенное отличие только что сформулированной задачи от задачи Штейнера (в ее графовой постановке) состоит в том, что в новой задаче множество вершин при поиске остовного дерева наименьшего веса не меняется. Поэтому алгоритм Краскала и дает лишь некоторое приближение решения задачи Штейнера.

При описании алгоритма будем использовать способ хранения данных, называемый очередью. Элементы данных в очереди упорядочиваются по времени поступления. Элементы можно добавлять в очередь и извлекать из очереди. В каждый момент времени доступен только один элемент, который был помещен в очередь раньше других, — "голова" очереди. При добавлении новый элемент помещается в "хвост" очереди, т.е. работа ведется по обычному для очереди правилу — "первым пришел — первым вышел". Чтобы извлечь из очереди некоторый элемент, не доступный в текущий момент, надо извлечь все ранее поступившие элементы, начиная с "головы" очереди.

Рассмотрим алгоритм нахождения остовного дерева наименьшего веса (алгоритм Краскала). Пусть дан связный неориентированный граф с числовыми неотрицательными весами ребер. Вес ребра е обозначим .

В результате работы алгоритма получим остовное дерево графа является наименьшей.

Отсортируем все ребра исходного графа по возрастанию весов и сформируем из них очередь так, чтобы в "голове" очереди находилось ребро с наименьшим весом, а в "хвосте" — с наибольшим и веса ребер не убывали от "головы" очереди к "хвосту".

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

На последующих шагах алгоритма из очереди извлекается по одному ребру. Если это ребро соединяет вершины, принадлежащие разным компонентам текущего остовного леса, то оно добавляется к текущему множеству ребер искомого дерева, а указанные компоненты сливаются в одну. Иначе ребро отбрасывается. Процесс повторяется до тех пор, пока число компонент остовного леса не окажется равным 1. Можно показать, что эта компонента и будет искомым остовным деревом наименьшего веса.

Переходим к формальному описанию алгоритма Краскала.

1. Множество ребер искомого остовного дерева полагаем пустым .

2. Формируем множество , элементами которого являются множества вершин, соответствующих компонентам исходного остовного леса. Каждая такая компонента состоит из единственной вершины.

3. Сортируем множество ребер , элементами которой являются ребра графа 4. Если множество содержит более одного элемента (т.е. остовный лес состоит из нескольких компонент) и очередь не пуста, переходим на шаг 5 , если иначе — на шаг 7 .

5. Извлекаем из очереди ребро и из , то переходим на шаг 6 , если иначе, то отбрасываем извлеченное ребро и возвращаемся на шаг 4 .

6. Объединяем множества вершин и (полагая ), удаляем множества и из множества и добавляем в множество . Добавляем ребро . Возвращаемся на шаг 4 .

7. Прекращаем работу. Множество есть множество ребер полученного остовного дерева.

Доказательство корректности алгоритма Краскала, т.е. доказательство того факта, что выдаваемое алгоритмом остовное дерево действительно является остовным деревом наименьшего веса, мы не приводим.

На рис. 5.19,(а-д) для неориентированного графа показана последовательность построения остовного дерева наименьшего веса. Заметим, что результат работы алгоритма в общем случае зависит от порядка следования ребер одинакового веса в очереди. Предположим, что после сортировки первым в очереди находится ребро с весом 2.

Исходный граф изображен на рис. 5.19,а. На рис. 5.19,б проиллюстрирован результат выполнения первого шага алгоритма. На рис. 5.19, в показан результат добавления следующего ребра с весом 2 из очереди. На рис. 5.19,г приведен результат добавления ребра с весом 3. Если следующим в очереди ребром будет , оно будет отброшено. Дальнейший ход работы алгоритма зависит от того, в каком порядке в очереди размещены ребра и с весами 4. Любое из них может быть добавлено в множество ребер остовного дерева, и на этом алгоритм закончит работу. На рис. 5.19,д приведено остовное дерево, полученное после добавления ребра .

Отметим, что для приведенного графа оба ребра с весом 2 войдут в остовное дерево независимо от порядка их расположения в очереди после сортировки, а ребро не войдет ни в какое остовное дерево наименьшего веса.

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