Как работает алгоритм Крускала для построения минимального остовного дерева?

Алгоритм Крускала предназначен для построения минимального остовного дерева взвешенного связного неориентированного графа. ru.wikipedia.org

Работа алгоритма начинается с вырожденного леса, где каждое дерево состоит из одной вершины. intuit.ru Затем выполняется операция объединения двух деревьев (самыми короткими рёбрами). intuit.ru

Процесс происходит следующим образом: www.e-maxx-ru.1gb.ru

1. Перед началом выполнения алгоритма все рёбра сортируются по весу (в порядке неубывания). www.e-maxx-ru.1gb.ru
2. Перебираются все рёбра от первого до последнего (в порядке сортировки). www.e-maxx-ru.1gb.ru
3. Если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро добавляется к ответу. www.e-maxx-ru.1gb.ru
4. По окончании перебора всех рёбер все вершины окажутся принадлежащими одному поддереву, и ответ найден. www.e-maxx-ru.1gb.ru

Если обе вершины рассматриваемого ребра принадлежат одному и тому же связному компоненту, то такое ребро отбрасывается — в противном случае образуется цикл. cs.mipt.ru

Алгоритм останавливается в двух случаях: intuit.ru

1. Если найдено определённое количество рёбер (например, V–1), то остовное дерево уже построено, и можно остановиться. intuit.ru
2. Если просмотрены все вершины, но не найдено V–1 древесных рёбер, то это означает, что граф не является связным. intuit.ru