Комбинаторные алгоритмы для программистов


Остовные деревья - часть 2


Мы начинаем с некоторой произвольной вершины
a
в заданном графе. Пусть
(a,b)
- ребро с наименьшим весом, инцидентное
a
; ребро
(a,b)
включается в дерево. Затем среди всех ребер, инцидентных либо
a
, либо
b
, выбираем ребро с наименьшим весом и включаем его в частично построенное дерево. В результате этого в дерево добавляется новая вершина, например,
c
. Повторяя процесс, ищем наименьшее ребро, соединяющее
a
,
b
или
c
с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из
G
не будут включены в дерево, то есть пока дерево не станет остовным.

Наихудшим для этого алгоритма будет случай, когда

G
- полный граф (то есть когда каждая пара вершин в графе соединена ребром); в этом случае для того, чтобы найти ближайшего соседа, на каждом шаге нужно сделать максимальное число сравнений. Чтобы выбрать первое ребро, мы сравниваем веса всех
\left| V \right| - 1
ребер, инцидентных вершине
a
, и выбираем наименьшее; этот шаг требует
\left| V \right| - 2
сравнений. Для выбора второго ребра мы ищем наименьшее среди возможных
2(\left| V \right| - 2)
ребер (инцидентных
a
или
b
) и делаем для этого
2(\left| V \right| - 2) - 1
сравнений. Таким образом, ясно, что для выбора
i
-го ребра требуется
i(\left| V \right| - i) - 1
сравнений, и поэтому в сумме потребуется
\sum\limits_{i = 1}^{\left| V \right| - 1} {[i(\left| V \right| - i) - 1] = \frac{1} {6}\left| V \right|^3 + O(\left| V \right|^2 )}
сравнений для построения минимума остовных деревьев.




Начало  Назад  Вперед



Книжный магазин