Министерство образования Украины
Одесский Национальный Политехнический Университет
Кафедра
Расчётно-графическая работа №1
Тема: «Aлгоритм Дейкстры-Прима в поиске минимального остовного дерева»
Выполнил студент 2 курса
Руководитель:
Дата выполнения: 24.11.2008
Оценка:
Одесса – 2008
Постановка задачи:
Исследовать алгоритм Дейкстры-Прима поиска минимального остовного древа:
1) Привести детальное описание алгоритма;
2) Описать алгоритм при помощи псевдокода;
3) Развернуто определить вычислительную сложность алгоритма;
4) Построить граф алгоритма и исследовать его на предмет возможности распараллеливания (провести топологическую сортировку).
Выполнение работы:
Общие сведения:
Алгоритм поиска минимального остовного дерева
Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер минимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент. МОД для связного графа можно найти с помощью грубой силы. Поскольку множество ребер МОД является подмножеством в множестве ребер исходного графа, можно просто перебрать все возможные подмножества и найти среди них МОД. Нетрудно видеть, что это чрезвычайно трудоемкий процесс. В множестве из N ребер имеется 1N подмножеств. Для каждого из этих подмножеств мы должны будем проверить, что оно задает связный подграф, охватывающий все вершины исходного, и не содержит циклов, а затем сосчитать его вес. Процесс можно ускорить после того, как найдено первое остовное дерево. Никакое подмножество ребер, полный вес которого больше, чем у уже найденного наилучшего остовного дерева, не может нам подойти, поэтому нет необходимости проверять связность, ацикличность и охват всех вершин. Однако даже и при этом улучшении сложность метода грубой силы будет порядка O(2N).
Алгоритм Дейкстры—Прима
В конце 1950-х годов Эдгар Дейкстра и Прим, работая и публикуя
свои результаты независимо друг от друга, предложили следующий алгоритм построения МОД.
Воспользуемся для поиска МОД так называемым жадным алго-
ритмом. Жадные алгоритмы действуют, используя в каждый момент
лишь часть исходных данных и принимая лучшее решение на основе
этой части. В нашем случае мы будем на каждом шаге рассматривать
множество ребер, допускающих присоединение к уже построенной части остовного дерева, и выбирать из них ребро с наименьшим весом.
Повторяя эту процедуру, мы получим остовное дерево с наименьшим
весом.
Разобьем вершины графа на три класса: вершины, вошедшие в уже
построенную часть дерева, вершины, окаймляющие построенную часть, и еще не рассмотренные вершины. Начнем с произвольной вершиныграфа и включим ее в остовное дерево. Поскольку результатом построения будет некорневое дерево, выбор исходной вершины не влияет на окончательный результат (конечно, если МОД единственно). Все вершины, соединенные с данной, заносим в кайму. Затем выполняется цикл поиска ребра с наименьшим весом, соединяющего уе построенную часть остовного дерева с каймой; это ребро вместе с новой вершиной добавляется в дерево и происходит обновление каймы. После того, как в дерево попадут все вершины, работа будет закончена.
Вот как выглядит алгоритм:
выбрать начальный узел
сформировать начальную кайму, состоящую из вершин,
соседних с начальным узлом
while в графе есть вершины, не попавшие в дерево do
выбрать ребро из дерева в кайму с наименьшим весом
добавить конец ребра к дереву
изменить кайму, для чего
добавить в кайму вершины, соседние с новой
обновить список ребер из дерева в кайму так,
чтобы он состоял из ребер наименьшего веса
end while
На рис. 6.5 описано исполнение алгоритма на конкретном приме-
ре. В начале процесса мы выбираем произвольный узел А. Как мы
уже говорили, при другом выбореначальной вершины результат будет
тем же самым, если МОД единственно. Исходный граф изображен на
рис. 6.5 (а) и, как уже упоминалось, мы начинаем построение МОД с
вершины А. Все вершины, непосредственно связанные с А, образуют исходную кайму. Видно, что ребро наименьшего веса связывает узлы Аи В, поэтому к уже построенной части МОД добавляется вершина В
вместе с ребром АВ. При добавлении к дереву вершины В (рис. 6.5(в))
мы должны определить, не следует ли добавить к кайме новые верши-
ны. В результате мы обнаруживаем, что это необходимо проделать
с вершинами Е и G. Поскольку обе эти вершины соединены только с
вершиной В уже построенной части дерева, мы добавляем соединяю-
щие ребра к списку рассматриваемых на следующем шаге. Здесь же
необходимо проверить, являются ли ребра, ведущие из вершины А в С, D и F, кратчайшими среди ребер, соединяющих эти вершины с дере-
вом, или есть более удобные ребра, исходящие из В. В исходном графевершина В не соединена непосредственно ни с С, ни с F, поэтому дляних ничего не меняется. А вот ребро BD короче ребра AD, и поэтомудолжно его заменить. Наименьший вес из пяти ребер, идущих в кайму, имеет ребро BE, поэтому к дереву нужно добавить его и вершину Е(рис. 6.5 (г)). Вес ребра EG меньше веса ребра BG, поэтому оно заме-щает последнее. Из четырех ребер, ведущих в кайму, наименьший вес имеет АС, поэтому следующим к дереву добавляется оно. Добавление к остовному дереву вершины С и ребра АС (рис. 6.5 (д)) не приводит к изменению списка ребер.
Затем мы выбираем ребро AF и добавляем его к дереву вместе с
вершиной F. Кроме того, мы меняем список связей, поскольку вес ре-
бра FD меньше веса ребра BD, а вес ребра FG меньше веса ребра EG.
В получившейся кайме (рис. 6.5 (е)) ребро FD имеет наименьший вес
среди оставшихся, и оно добавляется следующим.
Теперь осталось добавить к дереву всего один узел (рис. 6.5 (ж)).
После этого процесс завершается, и мы построили МОД с корнем в
вершине А (рис. 6.5 (з)).
Вывод:
Проделав расчётно-графическую работу, мы научились анализировать алгоритмы, строить их графы, определять их вычислительную сложность и записывать их на псевдокоде. По результатам топологической сортировки мы определили возможность распараллеливания алгоритма.
