Остовное дерево связного неориентированного графа G — это дерево, минимально включающее в себя все вершины G. Граф может иметь много связующих деревьев.
пример
Минимальное остовное дерево
Остовное дерево с присвоенным весом, меньшим или равным весу каждого возможного остовного дерева взвешенного связного и ненаправленного графа G, называется минимальным остовным деревом (MST). Вес связующего дерева — это сумма всех весов, назначенных каждому ребру связующего дерева.
пример
Алгоритм Крускала
Алгоритм Крускала — это жадный алгоритм, который находит минимальное остовное дерево для связанного взвешенного графа. Он находит дерево этого графа, которое включает в себя каждую вершину, и общий вес всех ребер в дереве меньше или равен каждому возможному остовному дереву.
Алгоритм
Шаг 1 — Расположите все ребра данного графа G(V,E) в неубывающем порядке по весу ребра.
Шаг 2 — Выберите наименьшее взвешенное ребро на графике и проверьте, образует ли оно цикл с остовным деревом, сформированным до сих пор.
Шаг 3 — Если цикла нет, включите это ребро в связующее дерево, иначе отбросьте его.
Шаг 4 — Повторите Шаг 2 и Шаг 3 до тех пор, пока в остовном дереве не останется (V−1) количество ребер.
проблема
Предположим, что мы хотим найти минимальное остовное дерево для следующего графа G, используя алгоритм Крускала.
Решение
Из приведенного выше графика мы строим следующую таблицу —
| Край | Пара вершин | Крайний вес |
|---|---|---|
| E1 | (а, б) | 20 |
| E2 | (а, в) | 9 |
| E3 | (а, г) | 13 |
| E4 | (До нашей эры) | 1 |
| E5 | (б, д) | 4 |
| E6 | (б, е) | 5 |
| E7 | (CD) | 2 |
| E8 | (д, д) | 3 |
| E9 | (д, ж) | 14 |
Теперь мы переставим таблицу в порядке возрастания веса ребра —
| Край | Пара вершин | Крайний вес |
|---|---|---|
| E4 | (До нашей эры) | 1 |
| E7 | (CD) | 2 |
| E8 | (д, д) | 3 |
| E5 | (б, д) | 4 |
| E6 | (б, е) | 5 |
| E2 | (а, в) | 9 |
| E3 | (а, г) | 13 |
| E9 | (д, ж) | 14 |
| E1 | (а, б) | 20 |
Поскольку мы получили все 5 ребер на последнем рисунке, мы останавливаем алгоритм, и это минимальное остовное дерево, и его общий вес составляет (1+2+3+5+9)=20.
Алгоритм Прима
Алгоритм Прима, открытый в 1930 году математиками Войтехом Ярником и Робертом С. Примом, является жадным алгоритмом, который находит минимальное остовное дерево для связанного взвешенного графа. Он находит дерево этого графа, которое включает в себя каждую вершину, и общий вес всех ребер в дереве меньше или равен каждому возможному остовному дереву. Алгоритм Прима быстрее на плотных графах.
Алгоритм
-
Инициализируйте минимальное остовное дерево с единственной вершиной, случайно выбранной из графа.
-
Повторяйте шаги 3 и 4, пока все вершины не будут включены в дерево.
-
Выберите ребро, которое соединяет дерево с вершиной, которой еще нет в дереве, чтобы вес ребра был минимальным, а включение ребра не образовывало цикл.
-
Добавьте выбранное ребро и вершину, которую оно соединяет с деревом.
Инициализируйте минимальное остовное дерево с единственной вершиной, случайно выбранной из графа.
Повторяйте шаги 3 и 4, пока все вершины не будут включены в дерево.
Выберите ребро, которое соединяет дерево с вершиной, которой еще нет в дереве, чтобы вес ребра был минимальным, а включение ребра не образовывало цикл.
Добавьте выбранное ребро и вершину, которую оно соединяет с деревом.
проблема
Предположим, что мы хотим найти минимальное остовное дерево для следующего графа G, используя алгоритм Прима.
Решение
Здесь мы начинаем с вершины «а» и продолжаем.
Это минимальное связующее дерево, и его общий вес составляет (1+2+3+5+9)=20.