В данной статье для реализации алгоритма будут рассмотрены:
1. Система хранения графа на основе List<>
2. Сортировка рёбер графа по весу
3. Система непересекающихся множеств
На просторах интернета есть множество ресурсов, посвященных данному алгоритму, однако все варианты реализации, встреченные мной, показались слишком сложными для понимания и использования. Хочу предложить более приближенный к реальности вариант.
План действий
1. Сортируем имеющиеся рёбра по весу.
2. Создаём новое множество и добавляем в него первое ребро.
3. Затем пытаемся добавить каждое новое ребро в имеющееся множество, если возникает цикл - пропускаем.
4. Итоговое множество рёбер и есть искомое минимальное остовное дерево.
По сути, это и есть формулировка алгоритма Краскала. Звучит совсем просто.
Самый весёлый пункт из имеющихся - третий. Потому что проверка на появление циклов на каждом шаге будет не сильно простым занятием. Его мы модифицируем при помощи системы непересекающихся множеств.
Но для начала давайте рассмотрим систему хранения графа в программе.