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

[pic 1]

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

Шаг 0. Из графа удаляются все ребра, получается остовной подграф, где все вершины изолированы.

Удалив все ребра данного графа, получаем семь изолированных вершин x1, x2, …, x8, составляющих остов графа.

Пусть a – x1, b – x2, c – x3, d – x4, e – x5, f – x6, g – x7, s – x8.

Шаг 1. Ребра ранжируются по возрастанию весов.

Проранжируем ребра данного графа по весу, получим следующую таб- лицу 1.

Таблица 1 – Ранжированные по весу ребра графа G

Шаг 2. Выбирается ребро, имеющее наименьший вес, и включается в фор- мируемое остовное дерево.

Наименьший вес 1 имеет ребро (х5, х7) – включаем его в остовное дерево.

Шаг 3. Из оставшихся ребер выбирается снова то, которое имеет мини- мальный вес, и включается в остовное дерево, если при этом не образуются циклы.

1. Наименьший вес 2 имеет ребро (x2, x8) и (x5, x8)– включаем в дерево ребро (x2, x8).
2. Следующий наименьший вес 4 имеет ребро (x5, x6) и (x4, x8)– включаем (x4, x8) в остовное дерево.
3. Следующий наименьший вес 5 имеет ребро (х2, х3) – включаем его в остовное дерево.
4. Следующий наименьший вес 7 имеет ребро (х1, х2) и (х3, х7) – включаем (х1, х2) в остовное дерево.

Шаг 4. Конец алгоритма.

Поскольку все вершины включены в остовное дерево, конец алгоритма. Таким образом, искомое минимальное остовное дерево G содержит следующие ребра:

(х5, х7), (x2, x8), (x4, x8), (х2, х3), (х3, х7), (x1, x3), (х4, х6).

Общий вес ребер составляет min (G) = 1 + 2 + 2 + 4 + 4+ 5+ 7=25.

[pic 2]

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

Шаг 0. Из графа удаляются все ребра, получается остовной подграф, где все вершины изолированы.

Удалив все ребра данного графа, получаем семь изолированных вершин x1, x2, …, x8, составляющих остов графа.

Шаг 1. Включим любую вершину в формируемое остовное дерево. Включим в остовное дерево вершину х7.

Шаг 2. Рассмотрим все ребра, исходящие из вершин, включенных в остов к оставшимся вершинам, и из них выберем ребро с минимальным весом. Ее кон цевую вершину включим в остовное дерево.