Motivation
Урок 2 из 9 курса Алгоритм Прима — Алгоритмы на графах на Coddy.
В то время как алгоритм Краскала сортирует все ребра глобально и использует систему непересекающихся множеств (union-find), алгоритм Прима поддерживает одно растущее дерево и многократно выбирает ближайшую вершину за его пределами.
Зачем изучать алгоритм Прима?
- Плотные графы: алгоритм Прима с правильными структурами данных эффективен, когда ребер много.
- Свойство разреза: это наглядная иллюстрация того, почему самое дешевое ребро, выходящее из текущего дерева, всегда можно безопасно добавить.
- Два взгляда на одну проблему: сравнение алгоритмов Прима и Краскала углубляет ваше понимание минимальных остовных деревьев.
Поскольку все MST (минимальные остовные деревья) графа имеют одинаковые веса ребер, алгоритмы Прима и Краскала всегда выдают одинаковый общий вес.
Попробуйте сами
В этом уроке нет задания по программированию.
Проверьте себяВ этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.
