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

Определение 2.5. Вес остовного дерева взвешенного графа равен сумме весов, приписанных ребрам остовного дерева. Обозначение: .

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

Построение остова графа , имеющего наименьший вес, имеет широкое применение при решении некоторого класса задач прикладного характера. Приведем постановку одной из таких задач.

Пусть, например, граф служит моделью железнодорожной сети, соединяющей пункты …, , а – расстояние между пунктами и . Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все пункты …, были связаны между собой телеграфной сетью, протяженность которой была бы наименьшей.

Рассмотрим два способа построения минимального остовного дерева взвешенного графа: алгоритм Краскала и алгоритм Прима.

Идея метода Краскала состоит в том, чтобы формировать дерево , выбирая ребра с наименьшим весом так, чтобы не возникал цикл.