Алгоритм Краскала
Алгори́тм Кра́скала (алгоритм Крускала), алгоритм построения минимального остовного дерева во взвешенном связном неориентированном графе ([1]). Предложен (Kruskal. 1956) в 1956 г. Дж. Краскалом.
Алгоритм является жадным. Сначала, согласно алгоритму Краскала, рёбра графа сортируются по возрастанию веса, затем к изначально пустому множеству рёбер итеративно добавляется очередное ребро в данном порядке, если при его добавлении не образуется циклов. В результате получается минимальное остовное дерево.
С использованием структуры данных под названием «система непересекающихся множеств» (Galil. 1991. P. 319–344) можно получить временну́ю сложность для данного алгоритма. Здесь и обозначают множества рёбер и вершин графа , и – число рёбер и вершин в графе соответственно.
См. также «О большое».
Примечания
Литература
Источники
- Kruskal J. B. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical Society. – 1956. – Vol. 7, № 1. – P. 48–50.
- Galil Z. Data structures and algorithms for disjoint set union problems / Z. Galil, G. F. Italiano // ACM computing surveys. – 1991. – Vol. 23, № 3. – P. 319–344.
Дополнительная литература
- Алгоритмы : построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн ; пер. с англ. И. В. Красикова [и др.]. – 3-е изд. – Москва [и др.] : Вильямс, 2013.