Алгори́тм Кра́скала (алгоритм Крускала), алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе (Алгоритмы. 2013). Предложен (Kruskal. 1956) в 1956 г. Дж. Краскалом.

Алгоритм является жадным. Сначала, согласно алгоритму Краскала, рёбра графа сортируются по возрастанию веса, затем к изначально пустому множеству рёбер итеративно добавляется очередное ребро в данном порядке, если при его добавлении не образуется циклов. В результате получается минимальное остовное дерево.

С использованием структуры данных под названием «система непересекающихся множеств» (Galil. 1991. P. 319–344) можно получить временну́ю сложность $O(\vert E\vert \log \vert V\vert)$ для данного алгоритма. Здесь $E$ и $V$ обозначают множества рёбер и вершин графа $G,$ $\vert E\vert$ и $\vert V\vert$ – число рёбер и вершин в графе $G$ соответственно.

См. также «О большое».