Слайд 2
Определения
G(V,E) - связный неориентированный граф с заданной функцией
стоимости, отображающей ребра в вещественные числа.
Остовное дерево или каркас
(скелет) графа – это подграф, который :
1) содержит все вершины графа,
2) является деревом.
Нас интересуют алгоритмы построения минимального каркаса.
Минимальным каркасом является такой
каркас, сумма весов ребер которого минимальна.
Слайд 3
Алгоритм Краскала (Джозеф Крускал, 1956 год)
Сортируем
ребра графа по возрастанию весов.
Полагаем, что каждая вершина
относится к своей компоненте связности.
Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем:
если вершины, соединяемые данным ребром, лежат в разных компонентах связности, то объединяем эти компоненты в одну, а рассматриваемое ребро добавляем к минимальному остовному дереву;
если вершины, соединяемые данным ребром лежат в одной компоненте связности, то исключаем ребро из рассмотрения.
Если есть еще нерассмотренные ребра и не все компоненты связности объединены в одну, то переходим к шагу 3, иначе выход.
Слайд 4
Время работы:
Cортировка рёбер - O(|E|×log|E|)
Компоненты связности удобно
хранить в виде системы непересекающихся множеств.
Все операции в
таком случае займут O(E)
Слайд 5
Алгоритм Краскала
Вход. Неориентированный граф G= (V, Е) с
функцией стоимости с, заданной на его ребрах.
Выход. Остовное дерево
S= (V, Т) наименьшей стоимости для G.
Метод:
1. Т ; // остовное дерево (каркас)
2. VS ; // набор непересекающихся множеств вершин
3. построить очередь с приоритетами Q, содержащую все ребра из Е;
4. Для vV выполнить: добавить {v} к VS;
Пока |VS|> 1 выполнить:
6. { выбрать в Q ребро (v, w) наименьшей стоимости;
7. удалить (v, w) из Q;
8. если v и w принадлежат различным множествам W1 и W2 из VS то
9. { заменить W1 и W2 на W1W2 в VS;
10. добавить (v, w) к Т;
}
}
Слайд 7
Получившееся дерево является каркасом минимального
веса.
Введем массив меток вершин
графа Mark.
Начальные значения элементов массива равны номерам
соответствующих вершин
(Mark[i] = i; i 1.. N).
Ребро выбирается в каркас в том случае, если вершины,
соединяемые им, имеют разные значения меток.
Пример приведен на следующем слайде,
изменения Mark показаны в таблице.
Слайд 9
Алгоритм Прима
На каждом шаге вычеркиваем из графа дугу
максимальной стоимости с тем условием, что она не разрывает
граф на две или более компоненты связности, т.е. после удаления дуги граф должен оставаться связным.
Для того, чтобы определить, остался ли граф связным, достаточно запустить поиск в глубину от одной из вершин, связанных с удаленной дугой.
Условие окончания алгоритма?
Например, пока количество ребер больше либо равно количеству вершин, нужно продолжать, иначе – остановиться.
Слайд 11
Алгоритм Прима (другой)
Алгоритм впервые был открыт в 1930
году чешским
математиком Войцехом Ярником, позже переоткрыт
Робертом Примом в 1957
году, и, независимо от них,
Э. Дейкстрой в 1959 году.
Время работы алгоритма – O(V * E)
Можно улучшить – O(E log V + V2)
При использовании двоичной кучи – O(E log V)
При использовании фибоначчиевой кучи – O(E + V log V)
Слайд 12
1) Выбирается произвольная вершина - она будет корнем
остовного
дерева;
2) Измеряется расстояние от нее до всех других вершин,
т.е. находится
минимальное расстояние s от дерева до вершин, которые не включены в
дерево;
3) До тех пор, пока в дерево не добавлены все вершины делать:
- найти вершину u, расстояние от дерева до которой минимально;
- добавить ее к дереву;
- пересчитать расстояния от невключенных вершин до дерева
следующим образом:
если расстояние до какой-либо вершины от u меньше
текущего расстояния s от дерева, то в s записывается новое
расстояние.
Слайд 13
10
2
3
6
1
8
5
7
4
9
1
1
1
2
2
2
3
4
3
3
4
4
5
5
5
Запускаем алгоритм обхода графа, начиная с произвольной вершины.
В качестве контейнера выбираем очередь с приоритетами. Приоритет –
текущая
величина найденного расстояния до уже построенной части остовного дерева.
Релаксации подвергаются прямые и обратные ребра.
1
3
1
1
2
2
2
2
2
2
5
4
4
5
3
10
1
3
4
6
3
4
1
9
2
8
В результате работы получаем список
ребер остовного дерева вместе с весами
