Implementation (Part 2)
Урок 6 из 9 курса Алгоритм Краскала — Алгоритмы на графах на Coddy.
Теперь добавляйте самое дешевое безопасное ребро, пока MST не будет завершено.
Задание
СреднеТеперь постройте MST (минимальное остовное дерево).
Напишите функцию с именем kruskal, которая принимает n и плоский массив edges (тройки значений, неориентированный граф) связного графа и возвращает общий вес его минимального остовного дерева.
Многократно выбирайте самое дешевое неиспользованное ребро; если его конечные точки находятся в разных множествах, объедините их и добавьте вес ребра; в противном случае пропустите его.
Повторно используйте идею union-find из предыдущего урока.
Попробуйте сами
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// Напишите код здесь
return 0;
}
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
Все уроки раздела Алгоритм Краскала — Алгоритмы на графах
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity