Пусть G — (V, Е) — связный граф, в котором каждое ребро (v, w) помечено числом c(v, w), которое называется стоимостью ребра. Остовным деревом графа G называется свободное дерево, содержащее все вершины V графа G. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево. В этом разделе мы рассмотрим методы нахождения остовных деревьев минимальной стоимости.

Минимальное остовное дерево связного графа
(ребра минимального остовного дерева отдельно выделены цветом)

Приведенное дерево не единственное: удалив ребро (b, с) и заменив его ребром (a, h), мы получим другое остовное дерево с тем же весом 37.

В этой главе мы рассмотрим два алгоритма решения задачи поиска минимального остовного дерева — алгоритм Крускала (Kruskal) и алгоритм Прима (Prim). Каждый из них легко реализовать с помощью обычных бинарных пирамид, получив время работы О (E*lgV). При использовании фибоначчиевых пирамид алгоритм Прима можно ускорить до O (Е + V * lgV), что является весьма существенным ускорением при |V|<<|E|.

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