Построение минимального остова для неориентированной сети

Построение остова минимального веса с помощью алгоритма Краскала.
Рис. 16. Неориентированная сеть
(s1) Отсортируем множество ребер. Тогда исходная последовательность ребер имеет вид:
имеет вид:
v3,v5, v3,v6, v2,v4, v5,v6, v4,v5, v3,v4, v2,v5, v1,v4, v2,v3, v1,v2.
1-я итерация.
(s2) каждую вершину сети помещаем в отдельную ячейку:
C1=v1, C2=v2, C3=v3, C4=v4, C5=v5, C6=v6.
(s3) полагаем E'=∅;
(s4) удаляем первое ребро из имеющейся последовательности ребер:
e=v3,v5;
(s5) находим ячейки C3 и C5, содержащие концы ребра e.
Проверяем, верно ли условие C3=C5. Условие не верно. Следовательно,
- полагаем E'=E'∪e,
- объединяем соответствующие ячейки C3≔C3∪C5=v3,v5.
(s6) проводим проверку на завершение алгоритма: проверяем выполнение условия #E'=5. Условие не верно. Переходим к шагу (s4).
Результат работы алгоритма после 1-ой итерации приведен на рис. 17.
Рис. 17. Первое ребро искомого остова
2-я итерация.
(s4) удаляем ребро: e=v3,v6;
(s5) находим ячейки C3 и C6, содержащие концы ребра e. Проверяем, верно ли условие C3=C6. Условие не верно. Тогда полагаем E'=E'∪{e} и объединяем соответствующие ячейки: C3≔C3∪C6=v3,v5, v6;
(s6) проверяем, верно ли условие #E'=5 . Условие не верно. Переходим к шагу (s4) (рис. 18).

Рис. 18. Два ребра искомого остова
3-я итерация.
(s4) удаляем ребро: e=v2,v4;
(s5) находим ячейки C2 и C4, содержащие концы ребра e. Проверяем, верно ли условие C2=C4. Условие не верно. Тогда полагаем E'=E'∪{e} и объединяем соответствующие ячейки: C2≔C2∪C4=v2,v4;
(s6) проверяем, верно ли условие #E'=5. Условие не верно. Переходим к шагу (s4) (рис. 19).

Рис. 19. Три ребра искомого остова
4-я итерация.
(s4) удаляем ребро: e=v5,v6;
(s5) находим ячейки C3 и C3, содержащие концы ребра e. Проверяем, верно ли условие C3=C3. Условие верно. Переходим к шагу (s4).
5-я итерация.
(s4) удаляем ребро: e=v4,v5;
(s5) находим ячейки C2 и C3, содержащие концы ребра e. Проверяем, верно ли условие C2=C3. Условие не верно. Тогда полагаем E'=E'∪{e} и объединяем соответствующие ячейки: C2≔C2∪C3=v2,v3,v4,v5, v6;
(s6) проверяем, верно ли условие #E'=5. Условие не верно. Переходим к шагу (s4) (рис. 20).
Рис. 20. Четыре ребра искомого остова
6-я итерация.
(s4) удаляем ребро: e=v3,v4;
(s5) находим ячейки C2 и C2, содержащие концы ребра e