работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов (стр. 6 из 11)
Данные: матрица весов С(G) графа G.
Результат: матрица весов полученного остова, величина минимального остова.
1. Выберем в графе G ребро х минимального веса и построим граф G1, присоединяя к пустому графу Оn на множестве вершин V ребро х.
2. Если граф Gк уже построен и k < n-1, то строим граф Gк+1, присоединяя к графу Gк ребро y, имеющее минимальный вес среди ребер, не входящих в Gк и не составляющих циклов с ребрами из Gк.
В качестве иллюстрации рассмотрим нагруженный граф, изображенный на рис. 3а). На рис. 3б) представлено МОД данного графа (в скобках указан порядок присоединения ребер к МОД). Длина полученного МОД равна 10.
1 3 5 1 5  | |
 |  |
1 2 4 4 (1) (2) (4)
(3)
 |  |  |
4 5 2 3 3 4 2 3
а) б)
Рис. 3
ЗАДАНИЕ 15. Найти минимальный остов графа, используя алгоритм Прима.
Алгоритм Прима отличается от алгоритма Краскала только тем, что на каждом этапе строится не просто ациклический граф, а дерево.
А л г о р и т м П р и м а
Данные: матрица весов С(G) графа G.
Результат: матрица весов полученного остова, величина минимального остова.
1. Выберем в графе G ребро х = {v,w} минимального веса и построим дерево G1 = (V1,X1), полагая V1 = {v,w}, X1 = {х}.
2. Если дерево Gк уже построено и k < n-1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в Gк , выбираем ребро y минимального веса. Строим дерево Gк+1, присоединяя к Gк ребро y вместе с его не входящим в Gк концом.
Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа, такой, что каждая вершина графа просматривается только один раз, и переход от одной вершины к другой осуществляется по ребрам графа. Остановимся на двух стандартных методах такого перебора: поиск в глубину и поиск в ширину.
Рассмотрим метод поиска в глубину в неориентированном графе G. Идея этого метода состоит в следующем. Начинаем поиск с некоторой фиксированной вершины v0, присвоим ей ПГ-номер: ПГ(v0)=1. Затем выбираем произвольную вершину w, смежную с v0, присваиваем ей ПГ-номер: ПГ(w)=2, и повторяем процесс уже от вершины w. Предположим, что в результате выполнения нескольких шагов этого процесса мы пришли в вершину v и пусть ПГ(v)=k. Далее действуем в зависимости от ситуации следующим образом:
1) если имеется новая, т.е. еще непросмотренная вершина u, смежная с v, то, присваивая ей ПГ-номер: ПГ(u)=k+1, продолжаем поиск, начиная с вершины u;
2) если же не существует ни одной новой, т.е. непросмотренной вершины u, смежной с v, то считаем, что вершина v просмотрена и возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс поиска дальше.
Пример. 
7 1 8  |
 |
5 6 2 5 
9 
1 3 8 
3 6 
7 10 
2 9 104 4
а) б)
Рис. 4
Поиск в глубину завершается, когда все вершины графа просмотрены. Если в результате работы алгоритма произошел возврат в начальную вершину v0, но при этом не все вершины графа просмотрены, то необходимо выбрать произвольную вершину из непросмотренных и продолжить процесс поиска от этой вершины. В результате проведенного поиска пройденные ребра графа образуют вместе с пройденными вершинами одно или несколько деревьев. Если приписать пройденным ребрам ориентацию в соответствии с тем направлением, в каком они проходятся при выполнении поиска, то получится совокупность корневых деревьев, корнями которых служат начальные вершины.
Для графа, представленного на рис. 4 а), описанным методом были получены два корневых дерева, изображенных на рис 4б).
Рассмотрим идею поиска в ширину в неориентированном графе. Другое название этого метода – волновой.
Начинается поиск с произвольной вершины v. Ей приписывается номер 0. Вершину v считаем просмотренной и помещаем в очередь. Далее проходим все ребра {v, w}, инцидентные вершине v и ориентируем их из v в w. Всем вершинам w приписываем номер 1, считаем их просмотренными и помещаем в очередь. После этих действий вершина v удаляется из очереди.
Далее выбираем вершину u, которая находится в начале очереди. Пусть ей приписан номер k. Пройдем все ребра, соединяющие вершину u с еще непросмотренными вершинами w. Всем вершинам w присвоим номер k+1, будем считать их просмотренными и поместим в очередь в порядке их просмотра. После этого вершину u удаляем из очереди. Заканчивается поиск в ширину тогда, когда все вершины графа будут просмотрены.
Пример.
7(2)  |
5(1) 6(2) 
1(0) 3(1)