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

Мы начинаем с некоторой произвольной вершины

$a$

в заданном графе. Пусть

$(a,b)$

- ребро с наименьшим весом, инцидентное

$a$

; ребро

$(a,b)$

включается в дерево. Затем среди всех ребер, инцидентных либо

$a$

, либо

$b$

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

$c$

. Повторяя процесс, ищем наименьшее ребро, соединяющее

$a$

$b$

или

$c$

с некоторой другой вершиной графа. Процесс продолжается до тех пор, пока все вершины из

$G$

не будут включены в дерево, то есть пока дерево не станет остовным.

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

$G$

- полный граф (то есть когда каждая пара вершин в графе соединена ребром); в этом случае для того, чтобы найти ближайшего соседа, на каждом шаге нужно сделать максимальное число сравнений. Чтобы выбрать первое ребро, мы сравниваем веса всех

$\left| V \right| - 1$