Презентация на тему Алгоритм Краскала

Идеей этого метода есть постепенное построение остовного дерева за

счет соединения отдельных поддеревьев в единое. Сначала в пустое остовное дерево записывается ребро с наименьшим весом. Дальше делаем аналогично, т.е. добавляем ребра с наименьшим весом, которые ещё не были записаны в остовное дерево.

дерева как пустой и считаем, что все вершины создают

N поддеревьев, которые в свою очередь не имеют никаких ребер. Присвоим им имена порядкового номера соответствующих вершин.
2. Если же количество ребер в остовном дереве меньше чем (N-1), то среди свободных ребер данного графа, которые ещё не были задействованы в остовном дереве, определяем ребро с наименьшим весом. Таки ребром может быть ребро, которое принадлежит разным поддеревьям. В другом случаи переходи к пункту 4.
3. Добавляем новое ребро к остовному дереву, а вершинам, которые принадлежат двум поддеревьям, что объединяются, и к оторым принадлежат вершины текущего ребра, присвоить значение порядкового номера одного из поддеревьев.
4. Завершить алгоритм.

случае это ребро (4,6). И заносим его в массив.

действуем аналогично.
1
(4,6)
3
(5,6)
5
5
5
7
3
5
(1,2)
5
(3,4)
5
(3,7)
7
(2,7)