Структуры данных и алгоритмы (1021739), страница 54
Текст из файла (страница 54)
,'™" .',::!^'-' -;'•.••. •"'!:Листинг 7.3. Программа, реализующая алгоритм Крускала=-^:•.•,;,;8,, .С.'":-,;.procedure ~Kruskal ( V: SET; E: SET; var T: SET ) ;{ V — множество вершин, £ и Г — множества дуг }varпсотр: integer; { текущее количество компонент }edges: PRIORITYQUEUE;{множество дуг, реализованное как очередь с приоритетами)components: MFSET;{ множество V, сгруппированное в множество компонент }и,.
V. вершина;е: ребро;nextcomp: integer; { имя (номер) новой компоненты }исотр, vcomp: integer; { имена (номера) компонент }beginMAKENULL (Т) ;MAKENULL(edges) ;nextcomp:= 0;псотр:= число элементов множества V;for v е V do begin { инициализация компонент,содержащих по одной вершине из V }nextcomp:= nextcomp + 1;INITIAL(nextcomp, v, components)end;for e e Е do { инициализация очереди с приоритетами,содержащей ребра }INSERT(e, edges);while псотр > 1 do begin { рассматривается следующее ребро }е:= DELETEMIN(edges);пусть е = (и, v) ;исотр:= FIND<u, components);vcomp:= FIND(v, components);if ucomp <> vcomp then begin{ ребро е соединяет две различные компоненты }MERGE(u comp, vcomp, componen ts);ncomp:= лсотр - 1;INSERT(e, T)endendend; { Kruskal }Для реализации операторов, используемых в этой программе, можно применитьметоды, описанные в разделе 5.5. Время выполнения этой программы зависит отдвух факторов.
Если в исходном графе G всего е ребер, то для вставки их в очередь сприоритетами потребуется время порядка О(е loge).1 Каждая итерация цикла whileдля нахождения ребра с наименьшей стоимостью в очереди edges требует временипорядка O(loge). Поэтому выполнение всего этого цикла в самом худшем случае потребует времени О(е loge). Вторым фактором, влияющим на время выполнения программы, является общее время выполнения операторов MERGE и FIND, которое зависит от метода реализации АТД MFSET.
Как показано в разделе 5.5, существуютметоды, требующие времени и О(е loge), и О(е а(е)). В любом случае алгоритм Крускала может быть выполнен за время О(е loge).1Можно заранее создать частично упорядоченное дерево с е элементами за время О(е). Мырассмотрим этот прием в разделе 8.4 главы 8.216ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ7.3. Обход неориентированных графовВо многих задачах, связанных с графами, требуется организовать систематический обход всех вершин графа. Существуют два наиболее часто используемых методаобхода графов: поиск в глубину и поиск в ширину, о которых речь пойдет в этомразделе. Оба этих метода можно эффективно использовать для поиска вершин,смежных с данной вершиной.Поиск в глубинуНапомним, что в разделе 6.5 мы построили алгоритм dfs для обхода вершин ориентированного графа. Этот же алгоритм можно использовать для обхода вершин инеориентированных графов, поскольку неориентированное ребро (v, w) можно представить в виде пары ориентированных дуг v —> w и w —> v.Фактически построить глубинный остовный лес для неориентированного графа (т.е.совершить обход его вершин) даже проще, чем для ориентированного.
Во-первых, заметим, что каждое дерево остовного леса соответствует одной связной компоненте исходного графа, поэтому, если граф связный, его глубинный остовный лес будет состоятьтолько из одного дерева. Во-вторых, при построении остовного леса для орграфа мыразличали четыре типа дуг: дуги дерева, передние, обратные и поперечные дуги, а длянеориентированного графа в этой ситуации выделяют только два типа ребер: ребра дерева и обратные ребра. Так как для неориентированного графа не существует направления ребер, то, естественно, прямые и обратные ребра здесь не различаются и объединены общим названием обратные ребра. Аналогично, так как в остовном дереве длянеориентированного графа вершины не делятся на потомков и предков, то нет и перекрестных ребер.
В самом деле, пусть есть ребро (v, w) и предположим, что при обходеграфа вершина v достигнута раньше, чем вершина w. Тогда процедура dfs(v) не можетзакончиться раньше, чем будет рассмотрена вершина ш. Поэтому в остовном деревевершину w можно считать потомком вершины и. Но подобным образом, если сначалавызывается dfs(w), вершина v становится потомком вершины w.Итак, при обходе вершин неориентированного графа методом поиска в глубинувсе ребра делятся на следующие группы.1.Ребра дерева — это такие ребра (и, w), что при обходе графа процедура dfs(v) вызывается непосредственно перед процедурой dfs(w) или, наоборот, сначала вызывается процедура dfs(w), а затем сразу процедура dfs(v).2. Обратные ребра — такие ребра (v, w), что ни процедура dfs(w) не следует непосредственно за процедурой dfs(v), ни процедура dfs(v) не следует непосредственноза процедурой dfs(w) (т.е.
между вызовами этих процедур следуют вызовы нескольких других процедур dfs(x)).1Пример 7.6. Рассмотрим связный граф G на рис. 7.8,а. Остовное дерево для этогографа, полученное методом поиска в глубину, показано на рис. 7.8,6. Поиск был начат с вершины а, и мы придерживались соглашения изображать ребра деревасплошными линиями, а обратные ребра — пунктирными. Изображение остовного дерева начато от корня, и сыновья каждой вершины рисовались слева направо в томпорядке, в каком они впервые посещались в процедуре dfs.Опишем несколько шагов поиска в глубину для данного графа.
Процедура dfs(a)добавляет ребро (а, Ь) в остовное дерево Т, поскольку вершина Ь ранее не посещалась,и вызывает процедуру dfs(b). Процедура dfs(b) добавляет ребро (b, d) в остовное дере1Здесь приведены конструктивные определения ребер дерева и обратных ребер. Можно датьследующие, менее конструктивные, но более общие, определения: если при обходе графа достигнута вершина и, имеющая инцидентное ребро (v, w), то в случае, когда вершина w еще непосещалась во время этого обхода, данное ребро является ребром дерева, если же вершина wуже посещалась ранее, то ребро (v, w) — обратное ребро. — Прим. ред.7.3.
ОБХОД НЕОРИЕНТИРОВАННЫХ ГРАФОВ217во Г и в свою очередь вызывает процедуру dfs(d). Далее процедура dfs(d) добавляет востовное дерево ребро (d, е) и вызывает dfs(e). С вершиной е смежны вершины а, Ь иd, но они помечены как посещенные вершины.
Поэтому процедура dfs(e) заканчивается без добавления ребер в дерево Т. Процедура dfs(d) также находит среди вершин,смежных с вершиной d, только вершины, помеченные как "посещенные". Процедураdfs(d) завершается без добавления новых ребер в остовное дерево. Процедура dfs(b)проверяет оставшиеся смежные вершины а к е (до этого была проверена только вершина d).
Эти вершины посещались ранее, поэтому процедура dfs(b) заканчиваетсябез добавления новых ребер в дерево Т. Процедура dfs(a), продолжая работу, находитновые вершины, которые ранее не посещались. Это вершины с, f и g. DРис. 7.8. Граф и остовное дерево, полученное при обходе его вершин методомпоиска в глубинуПоиск в ширинуДругой метод систематического обхода вершин графа называется поиском в ширину. Он получил свое название из-за того, что при достижении во время обхода любой вершины v далее рассматриваются все вершины, смежные с вершиной v, т.е.осуществляется просмотр вершин "в ширину". Этот метод также можно применить ик ориентированным графам.Так же, как и при применении поиска вглубь, посредством метода поиска в ширинупри обходе графа создается остовный лес. Если после достижения вершины х при рассмотрении ребра (х, у) вершина у не посещалась ранее, то это ребро считается ребромдерева.
Бели же вершина у уже посещалась ранее, то ребро (х. у) будет поперечнымребром, так как оно соединяет вершины, не связанные наследованием друг друга.В эскизе процедуры bfs1 (листинг 7.4), реализующей алгоритм поиска в ширину,ребра дерева помещаются в первоначально пустой массив Т, формирующий остовныйлес. Посещенные вершины графа заносятся в очередь Q. Массив mark (метка) отслеживает состояние вершин: если вершина v пройдена, то элемент mark[v] принимаетзначение visited (посещалась), первоначально все элементы этого массива имеют значение unvisited (не посещалась).
Отметим, что в этом алгоритме во избежание повторного помещения вершины в очередь пройденная вершина помечается как visitedдо помещения ее в очередь. Процедура bfs работает на одной связной компоненте, ес1Название процедуры bfs является сокращением от breadth-first search, что обозначает"поиск в ширину". — Прим.
ред.218ГЛАВА 7. НЕОРИЕНТИРОВАННЫЕ ГРАФЫли граф не односвязный, то эта процедура должна вызываться для вершин каждойсвязной компоненты.Листинг 7.4. Алгоритм поиска в ширинуprocedure bfs ( v ) ;{ bfs обходит все вершины, достижимые из вершины v }varQ: QUEUE { очередь для вершин }к, у: вершина;beginmark[v]:= visited;ENQUEUE (v, Q) ;while not EMPTY(Q) do beginx:= FRONT(Q);DEQUEUE(Q);for для каждой вершины у, смежной с вершиной х doif mark [у] = unvisited then beginmark[y]:= visited;ENQUEUE(y, Q) ;INSERT((x, y) , T)endendend; { bfs }Пример 7.7. Остовное дерево для графа из рис. 7.8,а, построенное методом поискав ширину, показано на рис.
7.9. Здесь обход графа начат с вершины а. Как и ранее,ребра дерева показаны сплошными линиями, а другие ребра — пунктирными. Отметим также, что дерево нарисовано от корня, а все сыновья любой вершины располагаются слева направо в порядке посещения их. РРис. 7.9. Остовное дерево для графа из рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
