Алгоритм "Алгоритм Прима"

Алгоритм Прима

Алгоритм Прима — это алгоритм в графах, который ищет минимальное остовное дерево во взвешенном связном графе.

Функция алгоритма состоит в том, чтобы найти кратчайший путь, соединяющий все вершины в соответствии с весами в графе, то есть сумму минимальных весов, соединяющих все вершины, которая также является минимальным остовным деревом в этом взвешенном графе.

Шаги алгоритма Прима

1. Выберите в качестве начальной точки одну из вершин ребра с наименьшим весом.
2. Найдите ребро с наименьшим весом из текущей вершины и запишите вершину как выбранную.
3. Повторяйте второй шаг, пока не будут найдены все вершины и минимальное остовное дерево графа.

Временная сложность алгоритма Прима

Предположим, у нас есть V для количества вершин в графе и E для количества ребер в графе.

В простой реализации, представленной графом матрицы смежности, для нахождения всех ребер с наименьшим весом требуется $O(V^{2})$ времени работы.

Используя простую двоичную кучу и представление списка смежности, время работы алгоритма Прима можно сократить до $O(E \log V )$ .

Если используется более сложная куча Фибоначчи, время работы может быть дополнительно сокращено до $O(E+V \log V)$ , что может значительно повысить скорость работы, когда связный граф достаточно плотный.

Пример алгоритма Прима

Найдите минимальное остовное дерево в соответствии с приведенным выше взвешенным связным графом.

Сначала выберите вершину A в качестве начальной точки. Вершины D, F, B соединены с A, а вес между AD наименьший, поэтому выбрано это ребро. В это время A, D — выбранные вершины, E, F, B — вершины, которые нужно выбрать, а H, G — невыбранные вершины.

Следующая вершина должна выбрать вершину с наименьшим весом из A и D, поэтому выбираем ребро AB. В этот момент A, D и B — выбранные вершины, E, F и G — вершины, которые нужно выбрать, а H — невыбранная вершина.

Следующая вершина должна выбрать вершину с наименьшим весом из A, D, B, поэтому выберите ребро DE. В это время A, D, B, E являются выбранными вершинами, F, G, H являются вершинами, которые необходимо выбрать, и невыбранных вершин нет.

Следующая вершина должна выбрать вершину с наименьшим весом из A, D, B, E, поэтому выберите ребро EH. На данный момент выбраны вершины A, D, B, E и H, вершины F и G должны быть выбраны, невыбранных вершин нет.

Следующая вершина должна выбрать вершину с наименьшим весом из A, D, B, E, H, поэтому выбираем ребро FH. В это время A, D, B, E, H, F являются выбранными вершинами, G является вершиной, которую нужно выбрать, и невыбранных вершин нет.

Наконец, осталась только одна вершина G, и та, у которой наименьший вес вершины G, — это HG. Теперь все вершины в графе связаны, красное связное ребро является минимальным остовным деревом, а сумма весов минимального остовного дерева равна 42.

Суммировать

Алгоритм Прима состоит в том, чтобы найти ребро с наименьшим весом посредством диффузии вершин, а пройденные вершины и ребра являются минимальным остовным деревом графа. Хранение графов в разных структурах данных может привести к непостоянной временной сложности.Временная сложность использования матрицы смежности составляет $O(V^{2})$ , временная сложность двоичной кучи и списка смежности равна $O(E \log V )$ .

PS:
Чистые горы и чистые воды начинаются с пыли, а знания ценнее усердия.
У меня есть вино, у тебя есть история?
Публичный аккаунт WeChat: "болтать".
Добро пожаловать в чат и поговорим о коде.