Алгоритм построения минимального покрывающего дерева прима

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

Алгоритм Прима (англ. Prim’s algorithm) — алгоритм поиска минимального остовного дерева (англ. minimum spanning tree, MST) во взвешенном неориентированном связном графе.

Идея

Данный алгоритм очень похож на алгоритм Дейкстры. Будем последовательно строить поддерево [math]F[/math] ответа в графе [math]G[/math] , поддерживая приоритетную очередь [math]Q[/math] из вершин [math]G \setminus F[/math] , в которой ключом для вершины [math]v[/math] является [math]\min\limits_w(uv)[/math] — вес минимального ребра из вершин [math]F[/math] в вершины [math]G \setminus F[/math] . Также для каждой вершины в очереди будем хранить [math]p(v)[/math] — вершину [math]u[/math] , на которой достигается минимум в определении ключа. Дерево [math]F[/math] поддерживается неявно, и его ребра — это пары [math]\left(v,p(v)\right)[/math] , где [math]v \in G \setminus \ \setminus Q[/math] , а [math]r[/math] — корень [math]F[/math] . Изначально [math]F[/math] пусто и значения ключей у всех вершин равны [math]+\infty[/math] . Выберём произвольную вершину [math]r[/math] и присвоим её ключу значение [math]0[/math] . На каждом шаге будем извлекать минимальную вершину [math]v[/math] из приоритетной очереди и релаксировать все ребра [math]vu[/math] , такие что [math]u \in Q[/math] , выполняя при этом операцию [math]\text[/math] над очередью и обновление [math]p(v)[/math] . Ребро [math]\left(v,p(v)\right)[/math] при этом добавляется к ответу.

Реализация

// [math]G[/math] — исходный граф // [math]w[/math] — весовая функция function [math]\mathtt():[/math] for [math]v \in V(G)[/math] [math]\mathtt[v]\ =\ \infty[/math] [math]\mathtt
[v]\ =[/math] null [math]r\ =[/math] произвольная вершина графа [math]G[/math] [math]\mathtt[r]\ =\ \mathtt[/math] [math]Q.\mathtt(V(G))[/math] while not [math]Q.\mathtt[/math] [math]v\ =\ Q.\mathtt()[/math] for [math]vu \in E(G)[/math] if [math]u \in Q[/math] and [math]\mathtt[u] \gt w(v, u)[/math] [math]\mathtt
[u]\ =\ v[/math] [math]\mathtt[u]\ =\ w(v, u)[/math] [math]Q.\mathtt(u, \mathtt[u])[/math] 

Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.
Чтобы упростить операцию [math]\mathrm[/math] можно написать кучу на основе сбалансированного бинарного дерева поиска. Тогда просто удалим вершину и добавим ее обратно уже с новым ключом. Асимптотика таких преобразований [math]O(\log n)[/math] . Если же делать с бинарной кучей, то вместо операции [math]\mathrm[/math] , будем всегда просто добавлять вершину с новым ключом, если из кучи достали вершину с ключом, значение которого больше чем у нее уже стоит, просто игнорировать. Вершин в куче будет не больше [math]n^2[/math] , следовательно, операция [math]\mathrm[/math] будет выполняться за [math]O(\log n^2)[/math] , что равно [math]O(\log n)[/math] . Максимальное количество вершин, которое мы сможем достать, равняется количеству ребер, то есть [math]m[/math] , поэтому общая асимптотика составит [math]O(m \log n)[/math] , что хорошо только на разреженных графах.

Пример

Рассмотрим работу алгоритма на примере графа. Пусть произвольно выбранная вершина — это вершина a.

Корректность

По поддерживаемым инвариантам после извлечения вершины [math]v\ (v \neq r)[/math] из [math]Q[/math] ребро [math]\left(v,p(v)\right)[/math] является ребром минимального веса, пересекающим разрез [math]\left(F,Q\right)[/math] . Значит, по лемме о безопасном ребре, оно безопасно. Алгоритм построения MST, добавляющий безопасные ребра, причём делающий это ровно [math]|V|-1[/math] раз, корректен.

Оценка производительности

Производительность алгоритма Прима зависит от выбранной реализации приоритетной очереди, как и в алгоритме Дейкстры. Извлечение минимума выполняется [math]V[/math] раз, релаксация — [math]O(E)[/math] раз.

Структура данных для приоритетной очереди	Асимптотика времени работы
Наивная реализация	[math]O(V^2+E)[/math]
Двоичная куча	[math]O(E\log)[/math]
Фибоначчиева куча	[math]O(V\log+E)[/math]

См. также

Источники информации

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн — Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом «Вильямс», 2010. — с.653 — 656.— ISBN 978-5-8459-0857-5 (рус.)
• Википедия — Алгоритм Прима
• Wikipedia — Prim’s algorithm
• MAXimal :: algo :: Минимальное остовное дерево. Алгоритм Прима

Источник

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

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

Как работает алгоритм Прима

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

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

Алгоритм Прима. Псевдокод.

Псевдокод для алгоритма Прима показывает, как мы создаем два набора вершин U и V-U. U содержит список вершин, которые были посещены, а V-U – список вершин, которые не были посещены. Один за другим мы перемещаем вершины из набора V-U в набор U, соединяя ребро с наименьшим весом.

Реализация алгоритма Прима в C ++

Программа ниже реализует алгоритм Прима в C ++. Несмотря на то, что используется матрица смежности для представления графа, этот алгоритм также может быть реализован с использованием списка смежности для повышения его эффективности.

#include #include using namespace std; #define INF 9999999 // number of vertices in grapj #define V 5 // create a 2d array of size 5x5 //for adjacency matrix to represent graph int G[V][V] = < , , , , >; int main () < int no_edge; // number of edge // create a array to track selected vertex // selected will become true otherwise false int selected[V]; // set selected false initially memset (selected, false, sizeof (selected)); // set number of edge to 0 no_edge = 0; // the number of egde in minimum spanning tree will be // always less than (V -1), where V is number of vertices in //graph // choose 0th vertex and make it true selected[0] = true; int x; // row number int y; // col number // print for edge and weight cout G[i][j]) < min = G[i][j]; x = i; y = j; >> > > > cout return 0; >
 
Запустив приведенный выше код, мы получим вывод в виде:
 
Edge : Weight 0 - 1 : 9 1 - 3 : 19 3 - 4 : 31 3 - 2 : 51
 
Алгоритм Прима vs Краскала
 
Алгоритм Краскала является еще одним популярным алгоритмом минимального оставного дерева, который использует другую логику для нахождения MST графа. Вместо того, чтобы начинать с вершины, алгоритм Краскала сортирует все ребра от малого веса к большему и продолжает добавлять самые нижние ребра, игнорируя те ребра, которые создают цикл.
 
 
Рекомендуем хостинг TIMEWEB
 
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
 
Рекомендуемые статьи по этой тематике
 
По статье задано0 вопрос(ов) 
 
Вам это нравится? Поделитесь в социальных сетях!
 
Источник
 
Алгоритм Краскала, Прима для нахождения минимального остовного дерева
 
Алгоритмы нахождения MST применимы в различных областях, начиная от кластеризации данных до построения компьютерных, транспортных сетей.
Я надеюсь, что вы после прочтения данной статьи, примерно понимали, как работают жадные алгоритмы нахождения MST.
 
Формальная постановка задачи
 
Имеется следующий неориентированный взвешенный граф. Назовем остовным деревом подграф, содержащий все вершины исходного графа, который является деревом. И задача состоит в том, чтобы найти такое остовное дерево, сумма рёбер которого минимальна. 
 
 
Неформальная постановка задачи
 
Представьте исходный граф без рёбер, теперь вам нужно как-то соединить все вершины между собой, чтобы можно было бы попасть из любой вершины в другую, не имея при этом циклов в получившемся графе с минимально возможной суммой весов включенных рёбер.
 
Алгоритм Краскала
 
Механизм, по которому работает данный алгоритм, очень прост. На входе имеется пустой подграф, который и будем достраивать до потенциального минимального остовного дерева. Будем рассматривать только связные графы, в другом случае при применении алгоритма Краскала мы будем получать не минимальное остовное дерево, а просто остовной лес.
 
 
Вначале мы производим сортировку рёбер по неубыванию по их весам.
 
Добавляем i-ое ребро в наш подграф только в том случае, если данное ребро соединяет две разные компоненты связности, одним из которых является наш подграф. То есть, на каждом шаге добавляется минимальное по весу ребро, один конец которого содержится в нашем подграфе, а другой - еще нет.
 
Алгоритм завершит свою работу после того, как множество вершин нашего подграфа совпадет с множеством вершин исходного графа.
 
 
Данный алгоритм называется жадным из-за того, что мы на каждом шаге пытаемся найти оптимальный вариант, который приведет к оптимальному решению в целом.
 
Разбор конкретного примера по шагам
 
Из представленного сверху графа, выпишем все его ребра в отсортированном порядке: 
 
1) D B; w = 2
2) D C; w = 6
3) A B; w = 7
4) A C; w = 8
5) C E; w = 9
6) D F; w = 9
7) F E; w = 10
8) B C; w = 11
9) D E; w = 11
 
И начнем по списку добавлять эти ребра в наш остов:
 
 
При добавлении в наше остовное дерево ребра A C, как вы можете заметить, образовывается цикл, поэтому мы просто пропускаем данное ребро.
 
По итогу у нас образовывается следующий подграф, и как вы заметили, мы соединили все вершины ребрами с минимально-возможными весами, а значит, нашли минимальное остовное дерево для нашего исходного графа.
 
 
Проводим проверку с помощью встроенного алгоритма для нахождения MST на graphonline, и видим, что подграфы идентичны. 
И да, из-за того, что при равенстве весов рёбер мы можем выбрать любое из них, конечные подграфы, являющиеся минимальными остовными деревьями, могут различаться с точностью до некоторых рёбер.
 
 
Суммарный вес искомого MST равен 33.
 
Реализация
 
Реализовать представленный алгоритм проще всего с помощью СНМ(система непересекающихся отрезков).
 
Вначале, как мы уже раннее говорили, необходимо отсортировать ребра по неубыванию по их весам. Далее с помощью вызовов функции make_set() мы каждую вершину можем поместить в свое собственное дерево, то есть, создаем некоторое множество подграфов. Дальше итерируемся по всем ребрам в отсортированном порядке и смотрим, принадлежат ли инцидентные вершины текущего ребра разным подграфам с помощью функции find_set() или нет, если оба конца лежат в разных компонентах, то объединяем два разных подграфа в один с помощью функции union_sets().
 
В итоге асимптотическая сложность данного алгоритма сводится к:
 
, где: 
sort() - 
make_set()- 
find_set - 
union_sets -
 
vector parent, rank; void make_set(int v) < parent[v] = v; rank[v] = 0; >int find_set(int v) < if (v == parent[v]) return v; return parent[v] = find_set(parent[v]); >void union_sets(int a, int b) < a = find_set(a); b = find_set(b); if (a != b) < if (rank[a] < rank[b]) swap(a, b); parent[b] = a; if (rank[a] == rank[b]) rank[a]++; >> struct Edge < int u, v, weight; bool operator<(Edge const& other) < return weight < other.weight; >>; int n; vector edges; int cost = 0; vector result; parent.resize(n); rank.resize(n); for (int i = 0; i < n; i++) make_set(i); sort(edges.begin(), edges.end()); for (Edge e : edges) < if (find_set(e.u) != find_set(e.v)) < cost += e.weight; result.push_back(e); union_sets(e.u, e.v); >>
 
Алгоритм Прима
 
Суть самого алгоритма Прима тоже сводится к жадному перебору рёбер, но уже из определенного множества. На входе так же имеется пустой подграф, который и будем достраивать до потенциального минимального остовного дерева.
 
 
Изначально наш подграф состоит из одной любой вершины исходного графа.
 
Затем из рёбер инцидентных этой вершине, выбирается такое минимальное ребро, которое связала бы две абсолютно разные компоненты связности, одной из которых и является наш подграф. То есть, как только у нас появляется возможность добавить новую вершину в наш подграф, мы тут же включаем ее по минимальмально возможному весу.
 
Продолжаем выполнять предыдущий шаг до тех пор, пока не найдем искомое MST.
 
 
Разбор конкретного примера
 
Выбираем чисто случайно вершину E, далее рассмотрим все ребра исходящие из нее, включаем в наше остовное дерево ребро C E; w = 9, так как данное ребро имеет минимальный вес из всех рёбер инцидентных множеству вершин нашего подграфа. Имеем следующее:
 
 
Теперь выборка производится из рёбер: 
D C; w = 6 
A C; w = 8 
F E; w = 10 
B C; w = 11 
D E; w = 11
 
То есть, в данный момент, мы знаем только о двух вершинах, соответственно, знаем о всех ребрах, исходящих из них. Про связи между другими вершинами, которые не включены в наш подграф, мы ничего не знаем, поэтому они на этом шаге не рассматриваются.
 
Добавляем в наш подграф ребро D C и по аналогии добаляем ребро D B . Получаем следующее:
 
 
Давайте добьем наш подграф до минимального остовного дерева. Вы, наверное, уже догадались о том, по каким ребрам мы будем связывать наши оставшиеся вершины: 
A и F.
 
Проводим последние штрихи и получили тот же самый подграф в качестве минимального остовного дерева. Но как мы раннее говорили, сам подграф ничего не решает, главное тут - множество рёбер, которые включены в наше остовное дерево.
 
 
Суммарный вес искомого MST равен 33.
 
Источник
Читайте также:  Дерево грушевое или грушовое