В данной статье для реализации алгоритма будут рассмотрены:

1. Система хранения графа на основе List<>

2. Сортировка рёбер графа по весу

3. Система непересекающихся множеств

На просторах интернета есть множество ресурсов, посвященных данному алгоритму, однако все варианты реализации, встреченные мной, показались слишком сложными для понимания и использования. Хочу предложить более приближенный к реальности вариант.

План действий

1. Сортируем имеющиеся рёбра по весу.

2. Создаём новое множество и добавляем в него первое ребро.

3. Затем пытаемся добавить каждое новое ребро в имеющееся множество, если возникает цикл - пропускаем.

4. Итоговое множество рёбер и есть искомое минимальное остовное дерево.

По сути, это и есть формулировка алгоритма Краскала. Звучит совсем просто.

Самый весёлый пункт из имеющихся - третий. Потому что проверка на появление циклов на каждом шаге будет не сильно простым занятием. Его мы модифицируем при помощи системы непересекающихся множеств.

Но для начала давайте рассмотрим систему хранения графа в программе.