Временная сложность
O(V²)
Алгоритм Прима находит минимальное остовное дерево (MST) для связного неориентированного взвешенного графа. MST соединяет все вершины с минимальной суммарной стоимостью рёбер.
Как это работает:
1. Выбрать любую вершину в качестве начального дерева
2. Найти ребро с минимальным весом, соединяющее дерево с вершиной, которая ещё не входит в него
3. Добавить это ребро и вершину в дерево
4. Повторять, пока все вершины не войдут в дерево
Временная сложность:
O(V²) при использовании матрицы смежности
O(E log V) при использовании двоичной кучи
Пространственная сложность: O(V)
Применение:
- Проектирование сетей (прокладка кабелей с минимальными затратами)
- Приближённые алгоритмы для NP-трудных задач
- Кластерный анализ
- Сегментация изображений
Алгоритм Прима — это жадный алгоритм, который каждый раз выбирает ребро с наименьшим весом для расширения дерева. Его можно сравнить с алгоритмом Краскала, который сначала сортирует все рёбра графа.
Похожие алгоритмы
Частые вопросы
- Что такое Алгоритм Прима?
- Алгоритм Прима находит минимальное остовное дерево (MST) для связного неориентированного взвешенного графа. MST соединяет все вершины с минимальной суммарной стоимостью рёбер.
- Какова сложность Алгоритм Прима?
- Время (среднее): O(V²) · Память: O(V)
- Для кого предназначена визуализация Алгоритм Прима?
- Визуализация Алгоритм Прима рассчитана на продвинутый уровень в категории «Графы». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Алгоритм Прима?
- В той же категории (Графы) вы можете изучить: Breadth-First Search, Depth-First Search, Dijkstra's Algorithm. Каждый из них имеет интерактивную визуализацию.