Структуры данных и алгоритмы (1021739), страница 53
Текст из файла (страница 53)
На рис. 7.3 показаны матрица смежности и списки смежности, представляющие граф из рис. 7.1,a. Dаbсd110 1 11 0 11 1 1 00100а. Матрица смежностииьwи„*f4ииКС-б. Списки смежностиРис. 7.3. Представления неориентированного графаОчевидно, что матрица смежности для неориентированного графа симметрична.Отметим, что в случае представления графа посредством списков смежности для существующего ребра (i, j) в списке смежности вершины i присутствует вершина /', а всписке смежности вершины j — вершина i.210ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ7.2. Остовные деревья минимальной стоимостиПусть G = (V, Е) — связный граф, в котором каждое ребро (и, и>) помечено числом c(v, w), которое называется стоимостью ребра.
Остовным деревом графа Gназывается свободное дерево, содержащее все вершины V графа G. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево. В этом разделе мы рассмотрим методы нахождения остовных деревьев минимальной стоимости.Пример 7.4. На рис.
7.4 показаны граф с помеченными ребрами и его остовноедерево минимальной стоимости. ОРис. 7.4. Граф и его остовное деревоТипичное применение остовных деревьев минимальной стоимости можнонайти при разработке коммуникационных сетей. Здесь вершины графа представляют города, ребра — возможные коммуникационные линии между городами, а стоимость ребер соответствует стоимости коммуникационных линий. Вэтом случае остовное дерево минимальной стоимости представляет коммуникационную сеть, объединяющую все города коммуникационными линиями минимальной стоимости.Свойство остовных деревьев минимальной стоимостиСуществуют различные методы построения остовных деревьев минимальнойстоимости. Многие из них основываются на следующем свойстве остовных деревьев минимальной стоимости, которое для краткости будем называть свойством ОДМС.
Пусть G = (V", Е) — связный граф с заданной функцией стоимости,определенной на множестве ребер. Обозначим через U подмножество множествавершин V. Если (и, v) — такое ребро наименьшей стоимости, что и е U ии е V \ U, тогда для графа G существует остовное дерево минимальной стоимости, содержащее ребро (и, v).Доказать это свойство нетрудно. Допустим противное: существует остовное дереводля графа G, обозначим его Т — (V, Е'), содержащее множество U и не содержащееребро (u, v), стоимость которого меньше любого остовного дерева для G, содержащегоребро (и, v).Поскольку дерево Т — свободное дерево, то из второго свойства свободных деревьев следует, что добавление ребра (и, v) к этому дереву приведет к образованию цикла.Этот цикл содержит ребро (и, и) и будет содержать другое ребро (и, v') такое, чтои € U и v е V \ U, как показано на рис. 7.5. Удаление ребра (и, v) приведет к разрыву цикла и образованию остовного дерева, чья стоимость будет не выше стоимостидерева Т, поскольку с(и, v) < с(и, v).
Мы пришли к противоречию с предположением, что остовное дерево Т — это дерево минимальной стоимости.7.2. ОСТОВНЫЕ ДЕРЕВЬЯ МИНИМАЛЬНОЙ СТОИМОСТИ211Рис. 7.5. Цикл в остовном деревеАлгоритм ПримаСуществуют два популярных метода построения остовного дерева минимальнойстоимости для помеченного графа G = (V, Е), основанные на свойстве ОДМС. Одинтакой метод известен как алгоритм Прима (Prim). В этом алгоритме строится множество вершин U, из которого "вырастает" остовное дерево. Пусть V = {1, 2, ..., л}. Сначала {/ = {!}. На каждом шаге алгоритма находится ребро наименьшей стоимости(и, и) такое, что и е U и и е V \ U, затем вершина v переносится из множества V \Uв множество U.
Этот процесс продолжается до тех пор, пока множество U не станетравным множеству V. Эскиз алгоритма показан в листинге 7.1, а процесс построенияостовного дерева для графа из рис. 7.4,а — на рис. 7.6.Листинг 7.1. Алгоритм Прима,:,,:.<:-.Wv:.:'•.•'..,'.'чУ'".'.'..I'-'.i'V.i •':'., '--'''-..:procedure Prim ( G: граф; var Т: множество ребер );varU: множество вершин;и, v. вершина;beginТ:= 0;U:= {!};while U * V do beginнахождение ребра (u, v) наименьшей стоимости и такого,что u £ У и v e V\U;Г:= Г u {(u, v)};U:= U U (v)endend; { Prim }Если ввести два массива, то можно сравнительно просто организовать на каждомшаге алгоритма выбор ребра с наименьшей стоимостью, соединяющего множества Uи V \ U. Массив CLOSEST[i] для каждой вершины i из множества V \ U содержитвершину из U, с которой он соединен ребром минимальной стоимости (это ребро выбирается среди ребер, инцидентных вершине i, и которые ведут в множество U).Другой массив LOWCOST[i] хранит значение стоимости ребра (i, CLOSEST[i]).На каждом шаге алгоритма просматривается массив LOWCOST, находится минимальное значение LOWCOST[k].
Вершина k принадлежит множеству V \ U и соединена ребром с вершиной из множества U. Затем выводится на печать ребро(k, CLOSEST[kJ). Так как вершина k присоединяется к множеству U, то вследствиеэтого изменяются массивы LOWCOST и CLOSEST. Программа на языке Pascal, реализующая алгоритм Прима, представлена в листинге 7.2. На вход программы посту212ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫпает массив С размера п х п, чьи элементы C[i, j] равны стоимости ребер (i, /). Еслиребра (i, j) не существуют, то элемент C[i, j\ полагается равным некоторому достаточно большому числу.После нахождения очередной вершины k остовного дерева LOWCOST[k] ложитсяравным infinity (бесконечность), очень большому числу, такому, чтобы эта вершинауже в дальнейшем не рассматривалась. Значение числа infinity должно быть большестоимости любого ребра графа.t©2бгдРис.
7.6. Последовательность построения остовного дерева алгоритмом. ПримаЛистинг 7.2. Программа выполнения алгоритма Примаprocedure Prim ( С: array[l..n, l..n] of real );{ Prim печатает ребра остовного дерева минимальной стоимостидля графа с вершинами {1, ..., п} и матрицей стоимости С)var((1)(2)(3)LOH'COST: array[l..n] of real;CLOSEST: array[l..n] of integer;i, j, k, miл: integer;{ i и j — индексы. При просмотре массива LOWCOSTk — номер найденной вершины, rain = LOWCOST{k} }beginfor i:= 2 to п do begin{ первоначально в множестве U только вершина 1 !,LOWCOST[i] := C[l, i] ;CLOSEST[i] -.= 1end;7.2.
ОСТОВНЫЕ ДЕРЕВЬЯ МИНИМАЛЬНОЙ СТОИМОСТИ213(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)for i:= 2 to л do begin{ поиск вне множества U наилучшей вершины k, имеющейинцидентное ребро, оканчивающееся в множестве U }min:= LOWCOST12] ;k: = 2;for j: = 3 to -n do> ,if LOWCOST[j] < min then beginmin: = LOWCOST[j];k: = jend;writeln(k, CLOSEST[k]); { вывод ребра на печать }LOKCOST[k]:= infinity; { k добавляется в множество U }for j:= 2 to л do { корректировка стоимостей в U }if (C[k, j] < LOWCOST[j}) and(LOWCOSTlj] < infinity) then beginLOWCOST[j]:= C[k, j];CLOSESTij] := kend':•endend; { Prim2Время выполнения алгоритма Прима имеет порядок О(л ), поскольку выполняется п — 1 итерация внешнего цикла строк (4) — (16), а каждая итерация этогоцикла требует времени порядка О(п) для выполнения внутренних циклов в строках (7) - (10) и (13) - (16).
Если значение га достаточно большое, то использование этого алгоритма не рационально. Далее мы рассмотрим алгоритм Крускаланахождения остовного дерева минимальной стоимости, который выполняется завремя порядка О(е loge), где е — количество ребер в данном графе. Если е значительно меньше иг, то алгоритм Крускала предпочтительнее, но если е близко к2п , рекомендуется применять алгоритм Прима.Алгоритм КрускалаСнова предположим, что есть связный граф G = (V, Е) с множеством вершинV- {1, 2, ..., п} и функцией стоимости с, определенной на множестве ребер Е.
В алгоритме Крускала (Kruskal) построение остовного дерева минимальной стоимости дляграфа G начинается с графа Т = (V, 0), состоящего только из га вершин графа G и неимеющего ребер. Таким образом, каждая вершина является связной (с самой собой)компонентой. В процессе выполнения алгоритма мы имеем набор связных компонент, постепенно объединяя которые формируем остовное дерево.При построении связных, постепенно возрастающих компонент поочередно проверяются ребра из множества Е в порядке возрастания их стоимости.
Если очередноеребро связывает две вершины из разных компонент, тогда оно добавляется в граф Т.Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается,так как его добавление в связную компоненту, являющуюся свободным деревом,приведет к образованию цикла. Когда все вершины графа G будут принадлежать одной компоненте, построение остовного дерева минимальной стоимости Т для этогографа заканчивается.Пример 7.5. Рассмотрим помеченный граф, представленный на рис. 7.4,а.
Последовательность добавления ребер в формирующееся дерево Т показана на рис. 7.7.Ребра стоимостью 1, 2, 3 и 4 рассмотрены первыми и все включены в Т, посколькуих добавление не приводит к циклам. Ребра (1, 4) и (3, 4) стоимостью 5 нельзявключить в Т, так как они соединяют вершины одной и той же компоненты(рис. 7.7,г) и поэтому замыкают цикл. Но оставшееся ребро (2, 3) также стоимостью5 не создает цикл. После включения этого ребра в Т формирование остовного деревазавершается.
D214ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫt ©Рис. 7.7. Последовательное формирование вставного дерева минимальной стоимости посредством алгоритма Крускала.:•.. 'Этот алгоритм можно реализовать, основываясь на множествах (для вершин и ребер) и операторах, рассмотренных в главах 4 и 5. Прежде всего, необходимо множество ребер Е, к которому можно было бы последовательно применять операторDELETEMIN для отбора ребер в порядке возрастания их стоимости. Поэтому множество ребер целесообразно представить в виде очереди с приоритетами и использоватьдля нее частично упорядоченное дерево в качестве структуры данных.Необходимо также поддерживать набор С связных компонент, для чего можноиспользовать следующие операторы.Оператор MERGE(A, В, С) объединяет компоненты А и В из набора С и результатобъединения помещает или в А, или в Б.12. Функция FIND(i), С) возвращает имя той компоненты из набора С, которая содержит вершину и.3. Оператор INITIAL(A, и, С) создает в наборе С новую компоненту с именем А, содержащую только одну вершину v.Напомним, что в разделе 5.5 для множеств, поддерживающих операторыMERGE и FIND, мы ввели абстрактный тип данных, который назвали MFSET.
В.эскизе программы (листинг 7.3), реализующей алгоритм Крускала, используетсяэтот тип данных.1.1Отметим, что операторы MERGE и FIND здесь несколько отличаются от одноименныхоператоров из раздела 5.5, поскольку сейчас С — параметр, указывающий, где находятсямножества А к В.7.2. ОСТОВНЫЕ ДЕРЕВЬЯ МИНИМАЛЬНОЙ СТОИМОСТИ215•••'...--:•••';•••••;. • .:.,;/.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
