Остовное дерево наименьшей стоимости (минимального веса)

Упорядочим ребра множества Е в порядке возрастания их веса (стоимости). Выберем ребро с наименьшим весом С₁ и включим в граф Т. Теперь в графе Т (п - 1) компонент содержит только по одной вершине, одна компонента содержит две вершины и одно ребро.

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

Если же ребро связывает две вершины из одной компоненты, то такое ребро отбрасывается, так как его добавление в связную компоненту, являющуюся свободным деревом, приведет к образованию цикла.

Когда все вершины графа будут принадлежать одной компоненте, построение остовного дерева минимального веса Т с (п - 1) ребрами заканчивается. Процесс построения остовного дерева минимального веса можно проследить на примере графа, приведенного на рис.2.

рис 2.

Алгоритм Прима

Наиболее простым алгоритмом поиска остовного дерева минимального веса является алгоритм Прима.

Алгоритм Прима заключается в следующем.

1. Вначале выбираем некоторую вершину v, остальные (n - 1) вершины графа отмечаются как невыбранные.

2. Определяются веса между выбранной вершиной v и остальными невыбранными вершинами.

3. Выбираем вершину с наименьшим весом до нее, фиксируем выбранные ребро и вес.

4. Выбранную вершину исключаем из перечня невыбранных, число выбранных вершин уменьшаем на 1.

5. Пункты 1 — 4 повторяем до тех пор, пока не будут выбраны все вершины, т.е. (n - 1) раз.

Процесс поиска остовного дерева наименьшего веса по алгоритму Прима можно проследить на примере графа, приведенного на рис. 3.

рис. 3