DAA - связующее дерево
А spanning tree - это подмножество неориентированного графа, все вершины которого соединены минимальным числом ребер.
Если все вершины соединены в графе, то существует хотя бы одно остовное дерево. В графе может существовать более одного остовного дерева.
Свойства
- Остовное дерево не имеет цикла.
- В любую вершину можно попасть из любой другой вершины.
пример
На следующем графике выделенные ребра образуют остовное дерево.
Минимальное связующее дерево
А Minimum Spanning Tree (MST)- это подмножество ребер связного взвешенного неориентированного графа, которое соединяет все вершины вместе с минимально возможным общим весом ребер. Для получения MST можно использовать алгоритм Прима или алгоритм Крускала. Следовательно, в этой главе мы обсудим алгоритм Прима.
Как мы уже говорили, один граф может иметь более одного остовного дерева. Если естьn количество вершин, остовное дерево должно иметь n - 1количество ребер. В этом контексте, если каждое ребро графа связано с весом и существует более одного остовного дерева, нам нужно найти минимальное остовное дерево графа.
Более того, если существуют какие-либо повторяющиеся взвешенные ребра, граф может иметь несколько минимальных остовных деревьев.
На приведенном выше графике мы показали остовное дерево, хотя это не минимальное остовное дерево. Стоимость этого остовного дерева составляет (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38.
Мы будем использовать алгоритм Прима, чтобы найти минимальное остовное дерево.
Алгоритм Прима
Алгоритм Прима - это жадный подход к поиску минимального остовного дерева. В этом алгоритме для формирования MST мы можем начать с произвольной вершины.
Algorithm: MST-Prim’s (G, w, r)
for each u є G.V
u.key = ∞
u.∏ = NIL
r.key = 0
Q = G.V
while Q ≠ Ф
u = Extract-Min (Q)
for each v є G.adj[u]
if each v є Q and w(u, v) < v.key
v.∏ = u
v.key = w(u, v)
Функция Extract-Min возвращает вершину с минимальной стоимостью ребра. Эта функция работает с min-heap.
пример
Используя алгоритм Прима, мы можем начать с любой вершины, давайте начнем с вершины 1.
Вершина 3 соединен с вершиной 1 с минимальной стоимостью края, следовательно, край (1, 2) добавляется в остовное дерево.
Далее край (2, 3) считается как минимум среди ребер {(1, 2), (2, 3), (3, 4), (3, 7)}.
На следующем этапе получаем преимущество (3, 4) а также (2, 4)с минимальной стоимостью. Край(3, 4) выбирается случайным образом.
Аналогично ребра (4, 5), (5, 7), (7, 8), (6, 8) а также (6, 9)выбраны. Поскольку все вершины посещены, алгоритм останавливается.
Стоимость остовного дерева составляет (2 + 2 + 3 + 2 + 5 + 2 + 3 + 4) = 23. В этом графе больше нет остовного дерева со стоимостью меньше, чем 23.