Implementation (Part 2)
Урок 6 из 9 курса Алгоритм Прима — Алгоритмы на графах на Coddy.
Теперь выращивайте дерево, всегда добавляя самое дешевое пересекающее ребро.
Задание
СреднеТеперь вырастите всё дерево целиком.
Напишите функцию с именем prim, которая принимает n и плоский массив edges (тройки значений, неориентированные ребра) связного графа и возвращает общий вес минимального остовного дерева (Minimum Spanning Tree), начиная построение дерева с вершины 0.
Поддерживайте флаг inTree для каждой вершины. На каждом этапе находите самое дешевое ребро, у которого ровно один конец находится в дереве, добавляйте его вес к общему результату и включайте внешний конец этого ребра в дерево.
Попробуйте сами
#include <stdlib.h>
int prim(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