Что делает: ищет MST в взвешенном неориентированном связном графе

Общая идея:

Удаляем рёбра из графа, помечаем каждую вершину как отдельную компоненту связности. Сортируем массив рёбер по возрастанию, и, если вершины находятся в разных компонентах связности и если не образуется цикл, добавляем в граф ребро с минимальным весом между этими вершинами. После добавления ребра, объединяем компоненты связности этих смежных вершин в одну большую компоненту связности, пока не получим MST

Реализация:

// псевдокод писала Я так что чекните если что не так!

int main() {
	for u из G(V) do
		u.component = v // для каждой вершины - своя компонента
	sort(vector<int> edges) // сортируем по возрастанию массив рёбер
	Kruskal()
}

Kruskal() {
	for edge из edges do
		if ((u,v) == edge) & (u.component != v.component)) { // если вершины
															// минимального ребра находятся в разных
															// компонентах связности, то
			MST.push_back(edge) // добавляем ребро в MST
			component_unite(u, v) // все вершины из компоненты u и v объединяем
														// в одну большую
		}
}

‼ Особенности алгоритма Краскала:

1. жадный алгоритм
2. есть модификация DSU (система непересекающихся множеств), ускоряющая работу алгоритма
3. на разреженных графах работает быстрее, чем алгоритм Прима
4. чаще всего на практике используется Краскал, а не Прим

Визуализация: этим я займусь чуть попозже