Главная Промышленная автоматика.

Листинг 7.3. Программа, реализующая алгоритм Крускала

procedure Kruskal ( V: SET; Е: SET; var Т: SET ) ;

{ V - множество вершин, £ и Г - множества дуг } var

псотр: integer; { текущее количество компонент } edges: PRIORITYQUEUE;

{множество дуг, реализованное как очередь с приоритетами) components:MFSET;

{ множество V, сгруппированное в множество компонент } и, V. вершина; е: ребро;

nextcomp: integer; { имя (номер) новой компоненты } исотр, vcomp: integer; { имена (номера) кожюнент }

begin

МАКЕШЬЦГ) ,-MAKENULL(edges); nextcomp:= 0;

лсошр:= число элементов множества V; for V е V do begin { инициализация компонент, содержащих по одной вершине из V}

nextcomp: = nextcomp + 1;

INITIAL (nextcomp, V, components)

end;

for e e £" do { инициализация очереди с приоритетами,

содержащей ребра } INSERT(е, edges); wliile псотр > 1 do begin { рассматривается следующее ребро } е:= DELETEMIN(edges) ; пусть е = {и, V) ; исотр: = FIND(u, components); vcomp:= FIND (v, components) ; if ucomp <> vcomp then begin

{ ребро e соединяет две различные компоненты }

MERGE(ucomp, vcomp, components);

ncomp:= ncomp - 1;

INSERT(e, T)

end; { Kruskal }

Для реализации операторов, используемых в этой программе, можно применить методы, описанные в разделе 5.5. Время выполнения этой программы зависит от двух факторов. Если в исходном графе G всего е ребер, то для вставки их в очередь с приоритетами потребуется время порядка 0(е loge). Каждая итерация цикла while для нахождения ребра с наименьшей стоимостью в очереди edges требует времени порядка O(loge). Поэтому выполнение всего этого цикла в самом худшем случае потребует времени 0(е loge). Вторым фактором, влияющим на время выполнения программы, является общее время выполнения операторов MERGE и FIND, которое зависит от метода реализации АТД MFSET. Как показано в разделе 5.5, сушествуют методы, требующие времени и 0(е loge), и 0(е а(е)). В любом случае алгоритм Крускала может быть выполнен за время 0(е loge).

Можно заранее создать частично унорядоченное дерево с е элементами за время 0(e). Мы рассмотрим этот прием в разделе 8.4 главы 8.



7.3. Обход неориентированных графов

Во многих задачах, связанных с графами, требуется организовать систематический обход всех вершин графа. Сушествуют два наиболее часто используемых метода обхода графов: поиск в глубину и поиск в ширину, о которых речь пойдет в этом разделе. Оба этих метода можно эффективно использовать для поиска вершин, смежных с данной вершиной.

Поиск в глубину

Напомним, что в разделе 6.5 мы построили алгоритм dfs для обхода вершин ориентированного графа. Этот же алгоритм можно использовать для обхода вершин и неориентированных графов, поскольку неориентированное ребро (v, w) можно представить в виде пары ориентированных дуг г -> w и w -> г.

Фактически построить глубинный остовный лес для неориентированного графа (т.е. совершить обход его вершин) даже проше, чем для ориентированного. Во-первых, заметим, что каждое дерево остовного леса соответствует одной связной компоненте исходного графа, поэтому, если граф связный, его глубинный остовный лес будет состоять только из одного дерева. Во-вторых, при построении остовного леса для орграфа мы различали четыре типа дуг: дуги дерева, передние, обратные и поперечные дуги, а для неориентированного графа в этой ситуации выделяют только два типа ребф: ребра дерева и обратные ребра. Так как для неориентированного графа не сушествует направления ребер, то, естественно, прямые и обратные ребра здесь не различаются и объединены обшим названием обратные ребра. Аналогично, так как в остовном дереве для неориентированного графа вершины не делятся на потомков и предков, то нет и перекрестных ребер. В самом деле, пусть есть ребро (v, w) и предположим, что при обходе графа вершина v достигнута раньше, чем вершина w. Тогда процедура dfs(v)He может закончиться раньше, чем будет рассмотрена вершина ш. Поэтому в остовном дереве вершину W можно считать потомком вершины и. Но подобным образом, если сначала вызывается «(/«(и),вершина v становится потомком вершины w.

Итак, при обходе вершин неориентированного графа методом поиска в глубину все ребра делятся на следуюшие группы.

1. Ребра дерева - это такие ребра (и, w), что при обходе графа процедура dfs(v) вызывается непосредственно перед процедурой dfs(w) или, наоборот, сначала вызывается процедура dfs(w),a затем сразу процедура dfs(v).

2. Обратные ребра - такие ребра (v, w), что ни процедура dfa{w)Hei следует непосредственно за процедурой dfs(v), ни процедура rf/s(u)He следует непосредственно за процедурой dfs(.u))(T.e. между вызовами этих процедур следуют вызовы нескольких других процедур dfs{x)).

Пример 7.6. Рассмотрим связный граф G на рис. 7.8,а. Остовное дерево для этого графа, полученное методом поиска в глубину, показано на рис. 7.8,6. Поиск был начат с вершины а, и мы придерживались соглашения изображать ребра дерева сплошными линиями, а обратные ребра - пунктирными. Изображение остовного дерева начато от корня, и сыновья каждой вершины рисовались слева направо в том порядке, в каком они впервые посещались в процедуре dfs.

Опишем несколько шагов поиска в глубину для данного графа. Процедура dfs(a) добавляет ребро (а, Ь) в остовное дерево Т, поскольку вершина Ь ранее не посешалась, и вызывает процедуру dfs(b). Процедура dfs(b) добавляет ребро (Ь, d) в остовное дере-

Здесь приведены конструктивные определения ребер дерева и обратных ребер. Можно дать следующие, менее конструктивные, но более общие, определения: если при обходе графа достигнута верщина о, имеющая инцидентное ребро (v, w), то в случае, когда вершина w еще не посещалась во время этого обхода, данное ребро является ребром дерева, если же вершина w уже посещалась ранее, то ребро (v, w) - обратное ребро. - Прим. ред.



во г и в свою очередь вызывает процедуру d/s(d).Далее процедура dfs(d) добавляет в остовное дерево ребро (d, е) и вызывает dfs(e). С вершиной е смежны вершины а, Ь ж d, но они помечены как посешенные вершины. Поэтому процедура dfs(e) заканчивается без добавления ребер в дерево Т. Процедура dfs(d) таюке находит среди вершин, смежных с вершиной d, только вершины, помеченные как "посешенные". Процедура dfs(d) завершается без добавления новых ребер в остовное дерево. Процедура dfs(b) проверяет оставшиеся смежные вершины а к е (до этого была проверена только вершина d). Эти вершины посешались ранее, поэтому процедура dfs(b) заканчивается без добавления новых ребер в дерево Т. Процедура dfs(a), продолжая работу, находит новые вершины, которые ранее не посешались. Это вершины с, f ж g. □



Рис. 7.8. Граф и остовное дерево, полученное при обходе его вершин методом поиска в глубину

Поиск в ширину

Другой метод систематического обхода вершин графа называется поиском в ширину. Он получил свое название из-за того, что при достижении во время обхода любой вершины V далее рассматриваются все вершины, смежные с вершиной v, т.е. осушествляется просмотр вершин "в ширину". Этот метод тагсже можно применить и к ориентированным графам.

Так же, как и при применении поиска вглубь, посредством метода поиска в ширину при обходе графа создается остовный лес. Если после достижения вершины х при рассмотрении ребра (х, у) вершина у не посешалась ранее, то это ребро считается ребром дерева. Если же вершина у уже посешалась ранее, то ребро (х. у) будет поперечным ребром, так как оно соединяет вершины, не связанные наследованием друг друга.

В эскизе процедуры bfs (листинг 7.4), реализующей алгоритм поиска в ширину, ребра дерева помешаются в первоначально пустой массив Г, формирующий остовный лес. Посешенные вершины графа заносятся в очередь Q. Массив mark (метка) отслеживает состояние вершин: если вершина v пройдена, то элемент тагЩр\ принимает значение visited (посешалась), первоначально все элементы этого массива имеют значение unvisited (не посешалась). Отметим, что в этом алгоритме во избежание повторного помещения вершины в очередь пройденная вершина помечается как visited до помещения ее в очередь. Процедура bfs работает на одной связной компоненте, ес-

Название процедуры bfs является сокращением от breadth-first search, что обозначает "поиск в ширину". - Прим. ред.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 [68] 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0044