Поиск минимального связывающего дерева

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

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

Основные принципы построения минимального связывающего дерева (или кратчайшей связывающей сети) при наличии ограничений на локальные степени вершин ρ(m_i) следующие.

В начале любая произвольная вершина m_i ∈ M соединяется с ближайшей соседней, образуя исходное поддерево. (Для определенности построения минимального дерева можно начинать с ребра, инцидентного первой вершине m₁, или с минимального ребра). На каждом последующем шаге к строящемуся поддереву присоединяют очередное ребро минимально возможной длины, связывающее новую, еще не присоединенную вершину m_j с одной из вершин поддеревьев m_i ∈ M * , локальная степень которой ρ(m_i) < k.

Для реализации алгоритма составляют матрицу расстояний D = ||d_ij|| , элемент d_ij которой вычисляют по одной из формул (5.1) или (5.2). Просматривают элементы первой строки матрицы D и находят минимальный элемент. Пусть таким оказался элемент g-го столбца, тогда весь 1-й и g-й столбцы матрицы D исключаются из рассмотрения, а первое соединение проводится между точками m₁ и m_g. Просматриваются 1-я и g-я строки матрицы с оставшимися элементами. Из элементов этих строк находится минимальный. Предположим, что им оказался элемент, принадлежащий j-му столбцу. Если этот элемент находится на пересечении с первой строкой, то точку m_j соединяем с 1-й точкой (m₁), если же он находится на пересечении с g-й строкой, то точку m_j соединяем с g-й (m_g), после чего из матрицы D исключаем все элементы j-го столбца. Просматриваются 1-я, g-я и j-я строки и т. д.

Выполнение ограничения на локальную степень ρ(m_i) вершин обеспечивается проверкой в каждой просматриваемой i-ой строке числа уже выбранных для построения минимального дерева элементов – ρ(i) . При ρ(i) = ρ₀ все оставшиеся элементы i-й строки исключаются из рассмотрения, т.е. эта строка удаляется.

1. Вычислить элементы матрицы расстояний D = ||d_ij|| по одной из формул (5.1) или (5.2).

2. Найти минимальный элемент матрицы d_q,p = min d_ij, где i,j = 1,n; i ≠ j. Номера строки и столбца q и p, на пересечении которых он находится, определяют номера вершин m_q и m_p , соединяемых ребром.

3. Занести номера вершин во множество M * = , построенное ребро – во множество R = q,p>.

4. Подсчитать локальные степени ρ(m_g) и ρ(m_p) , подлежащих соединению на данном шаге вершин m_g и m_p.

5. Проверить условие ρ(m_g) < ρ₀ и ρ(m_p) < ρ₀ . Индексы вершин, для которых это условие не выполняется, указывают номера строк матрицы D, которые необходимо исключить из рассмотрения.

6. Найти d_r,t = min d_ij, . Здесь i ∈ M * , j ∉ M * , т. е. среди еще не вошедших в дерево вершин отыскать вершину m_t, минимально удаленную от некоторой вершины дерева m_r.

7. Дополнить множества M * = M * ∪ m_t; R = R ∪ r_r,t.

8. Проверить, все ли вершины графа соединены ветвями |R| = (n — 1) . Если условие выполняется, идти к 9, иначе – к 4.

Источник

Алгоритм Краскала, Прима для нахождения минимального остовного дерева

Алгоритмы нахождения 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.

Источник

Минимальное остовное дерево. Алгоритм Прима. Алгоритм Крускала

Остовным деревом графа называется дерево, которое можно получить из него путём удаления некоторых рёбер. У графа может существовать несколько остовных деревьев, и чаще всех их достаточно много.

На иллюстрации приведено одно из остовных деревьев (рёбра выделены синим цветом) решёткообразного графа.

Для взвешенных графов существует понятие веса остовного дерева, которое определено как сумма весов всех рёбер, входящих в остовное дерево. Из него натурально вытекает понятие минимального остовного дерева — остовного дерева с минимальным возможным весом.

Для нахождения минимального остовного дерева графа существуют два основных алгоритма: алгоритм Прима и алгоритм Крускала. Они оба имеют сложность \(O(M \log N)\), поэтому выбор одного из них зависит от ваших личных предпочтений. В этой лекции мы разберём оба.

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

Алгоритм Прима в идее и реализации очень похож на алгоритм Дейкстры. Как и в алгоритме Дейкстры, мы поддерживаем уже обработанную часть графа (минимального остовного дерева), и постепенно её расширяем за счёт ближайших вершин.

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

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

На иллюстрации красным цветом выделены рёбра, уже вошедшие в минимальный остов, а чёрным — текущие кандидаты, из которых выбирается ребро с минимальным весом.

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

Будем искать вес минимального остовного дерева. Для нахождения ближайшей вершины воспользуемся очередью с приоритетом (аналогично алгоритму Дейкстры), в которой будем хранить пары (расстояние от остова до вершины, номер вершины).

Различия в скорости работы

Хотя оба алгоритма работают за \(O(M \log N)\), существуют константные различия в скорости их работы. На разреженных графах (количество рёбер примерно равно количеству вершин) быстрее работает алгоритм Крускала, а на насыщенных (количество рёбер примерно равно квадрату количеству вершин) — алгоритм Прима (при использовании матрицы смежности).

На практике чаще используется алгоритм Крускала.

brestprog

Олимпиадное программирование в Бресте и Беларуси

Источник