Остовные деревья - часть 2
Мы начинаем с некоторой произвольной вершины
в заданном графе. Пусть
- ребро с наименьшим весом, инцидентное
; ребро
включается в дерево. Затем среди всех ребер, инцидентных либо
, либо
, выбираем ребро с наименьшим весом и включаем его в частично построенное дерево. В результате этого в дерево добавляется новая вершина, например,
. Повторяя процесс, ищем наименьшее ребро, соединяющее
,
или
с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из
не будут включены в дерево, то есть пока дерево не станет остовным.
Наихудшим для этого алгоритма будет случай, когда
- полный граф (то есть когда каждая пара вершин в графе соединена ребром); в этом случае для того, чтобы найти ближайшего соседа, на каждом шаге нужно сделать максимальное число сравнений. Чтобы выбрать первое ребро, мы сравниваем веса всех
ребер, инцидентных вершине
, и выбираем наименьшее; этот шаг требует
сравнений. Для выбора второго ребра мы ищем наименьшее среди возможных
ребер (инцидентных
или
) и делаем для этого
сравнений. Таким образом, ясно, что для выбора
-го ребра требуется
сравнений, и поэтому в сумме потребуется
сравнений для построения минимума остовных деревьев.
Содержание Назад Вперед