Алгоритм Крускала и кишки лабиринтов

Алгоритм Крускала (также алгоритм Краскала) - алгоритм, который преобразовывает связный неориентированный граф в минимальное остовное дерево. На самом деле пока что непонятно, что делает он, поэтому разберём поподробнее.

Итак, у нас есть связный граф, который хранится в виде списков рёбер (позже это будет важно). Предположим, у нас есть задание: нам нужно связать все вершины так, чтобы общий их вес будет минимальным. Если говорить более по-умному, нам нужно получить из графа именно это самое минимальное остовное дерево.