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

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

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

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

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

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

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

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

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

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

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

В результате работы алгоритма получим остовное дерево Т = (V, H) графа G, такое, что сумма является наименьшей.

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

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

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

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

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

1. Множество ребер Н искомого остовного дерева полагаем пустым (H = ∅).
2. Формируем множество V_S = {{v₁},..., {v_n}}, элементами которого являются множества вершин, соответствующих компонентам исходного остовного леса. Каждая такая компонента состоит из единственной вершины.
3. Сортируем множество ребер Е исходного графа по возрастанию весов и формируем очередь Q, элементами которой являются ребра графа G.
4. Если множество V_S содержит более одного элемента (т.е. остовный лес состоит из нескольких компонент) и очередь Q не пуста, переходим на шаг 5, если иначе — на шаг 7.
5. Извлекаем из очереди Q ребро е. Если концы ребра е принадлежат различным множествам вершин V_i и V_j из V_S, то переходим на шаг 6, если иначе, то отбрасываем извлеченное ребро и возвращаемся на шаг 4.
6. Объединяем множества вершин V_i и V_j (полагая W = = V_i ∪ V_j), удаляем множества V_i и V_j из множества V_S и добавляем в V_S множество W. Добавляем ребро е в множество Н. Возвращаемся на шаг 4.
7. Прекращаем работу. Множество Н есть множество ребер полученного остовного дерева.

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

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

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

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

Можно доказать, что наиболее трудоемким шагом в алгоритме Краскала является сортировка ребер графа по возрастанию весов. Как мы уже знаем, задачу сортировки п элементов нельзя решить быстрее, чем за время O(nlog₂n). Следовательно, сложность алгоритма Краскала оценивается числом O(|Е| log₂ |Е|), где |Е| — мощность множества ребер графа. Поскольку справедливо неравенство |Е| log₂ |E| ≤ |Е|¹, то алгоритм Краскала можно считать эффективным.