Структуры данных и алгоритмы (1021739), страница 49
Текст из файла (страница 49)
На рис. 6.13 показано транзитивное замыкание матрицы смежностиорграфа из рис. 6.10. D1231 11121111113Рис. 6.13. Транзитивное замыкание матрицы смежностиТранзитивное замыкание можно вычислить с помощью процедуры, подобнойFloyd, применяя на fe-м шаге следующую формулу к булевой матрице А:At[i, j] = Ai-ili, f] or (А4_![/, A] and Ak-i[k, j]).194ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫЭта формула устанавливает, что существует путь от вершины t до вершины /,проходящий через вершины с номерами, не превышающими k, только в следующихслучаях.1.Уже существует путь от вершины i до вершины ;, который проходит через вершины с номерами, не превышающими k - 1.Существует путь от вершины i до вершины k, проходящий через вершины с номерами, не превышающими k - 1, и путь от вершины k до вершины j, которыйтакже проходит через вершины с номерами, не превышающими k — 1.2.иЗдесь, как и в алгоритме Флойда, At[i, k] = At-i[*.
*] и At[k. j] = Ak-i[fc. Л. вычисления можно выполнять в одной копии матрицы А. Программа Warshall вычисления транзитивного замыкания показана в листинге 6.7.Листинг 6.7. Программа Warshall (^я вычисления транзитивного замыканияprocedure Warshall ( var A: array[l..n, l..n] of boolean;С: array[1..л, l . . n ] of boolean ) ;vari, j , k: integer;beginfor i:= 1 to л dofor j':= 1 to л doA[i, j]:= C[i, j];for k:= 1 to л dofor i:= 1 to л dofor j:= 1 to л doif A[i, j] = false thenA[i, j ] : = A[i, k] and A(k, j]end;{ Marshall }Нахождение центра ориентированного графаПредположим, что необходимо найти центральную вершину в орграфе. Эту задачутакже можно решить с помощью алгоритма Флойда.
Но сначала надо уточнить термин центральная вершина. Пусть v — произвольная вершина орграфа G = (V, Е).Эксцентриситет1 вершины v определяется кактах{минимальная длина пути от вершины w до вершины v}ire VЦентром орграфа G называется вершина с минимальным эксцентриситетом. Другими словами, центром орграфа является вершина, для которой максимальное расстояние (длина пути) до других вершин минимально.Пример 6.11. Рассмотрим помеченный орграф, показанный на рис.
6.14.В этом графе вершины имеют следующие эксцентриситеты.ВершиваЭксцентриситетаЬсdеИз этой таблицы видно, что центром данногооо6857орграфа является вершина d. П1В русской математической литературе наряду с термином "эксцентриситет" часто используется термин "максимальное удаление". — Прим. ред.6.4.
НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ МЕЖДУ ПАРАМИ ВЕРШИН195Найти центр орграфа сравнительно просто. Пусть С — матрица стоимостей дляорграфа G.1.2.3.Сначала применим процедуру Floyd (листинг 6.4) к матрице С для вычисленияматрицы А, содержащей все кратчайшие пути орграфа G.Находим максимальное значение в каждом столбце i матрицы А. Это значениеравно эксцентриситету вершины i.Находим вершину с минимальным эксцентриситетом. Она и будет центром графа G.Рис.
6.14. Помеченный орграфВремя выполнения этого процесса определяется первым шагом, для котороговремя имеет порядок О(п3). Второй шаг требует времени порядка О(п2), а третий — О(п).Пример 6.12. Матрица всех кратчайших путей для орграфа из рис. 6.14 представлена на рис. 6.15. Максимальные значения в каждом столбце приведены подматрицей. DaаЪсdеmax0оосоооооb10316od3203854205e76470Рис. 6.15.
Матрица кратчайших путей6.5. Обход ориентированных графовПри решении многих задач, касающихся ориентированных графов, необходимэффективный метод систематического обхода вершин и дуг орграфов. Таким методомявляется так называемый поиск в глубину — обобщение метода обхода дерева в прямом порядке. Метод поиска в глубину составляет основу многих других эффективных алгоритмов работы с графами. В последних двух разделах этой главы представлены различные алгоритмы, основанные на методе поиска в глубину.196ГЛАВА 6.
ОРИЕНТИРОВАННЫЕ ГРАФЫПредположим, что есть ориентированный граф G, в котором первоначально всевершины помечены меткой unvisited (не посещалась). Поиск в глубину начинается свыбора начальной вершины v графа G, для этой вершины метка unvisited меняетсяна метку visited (посещалась). Затем для каждой вершины, смежной с вершиной v икоторая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда всевершины, которые можно достичь из вершины v, будут "удостоены" посещения, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется.
Этот процесс продолжается до тех пор, покаобходом не будут охвачены все вершины орграфа G.Этот метод обхода вершин орграфа называется поиском в глубину, поскольку поиск не посещенных вершин идет в направлении вперед (вглубь) до тех пор, пока этовозможно. Например, пусть х — последняя посещенная вершина. Для продолженияпроцесса выбирается какая-либо нерассмотренная дуга х -» у, выходящая из вершины х. Если вершина у уже посещалась, то ищется другая вершина, смежная с вершиной х. Если вершина у ранее не посещалась, то она помечается меткой visited ипоиск начинается заново от вершины у.
Пройдя все пути, которые начинаются ввершине у, возвращаемся в вершину х, т.е. в ту вершину, из которой впервые быладостигнута вершина у. Затем продолжается выбор нерассмотренных дуг, исходящихиз вершины х, и так до тех пор, пока не будут исчерпаны все эти дуги.Для представления вершин, смежных с вершиной и, можно использовать списоксмежности L[v\, а для определения вершин, которые ранее посещались, — массивmark (метка), чьи элементы будут принимать только два значения: visited иunvisited. Эскиз рекурсивной процедуры dfs (от depth-first search — поиск в глубину), реализующей метод поиска в глубину, представлен в листинге 6.8.Чтобы применить эту процедуру к графу, состоящему из п вершин, надо сначалаприсвоить всем элементам массива mark значение unvisited, затем начать поиск вглубину для каждой вершины, помеченной как unvisited. Описанное можно реализовать с помощью следующего кода:for v:= I to n domark[v]:=unvisited;for v.
= 1 to л doif mark[v] = unvisited thendfs ( v )Отметим, что листинг 6.8 является только эскизом процедуры, который еще следует детализировать. Заметим также, что эта процедура изменяет только значениямассива mark.Листинг 6.8. Процедура поиска в глубину•' '•-' ' • ' ''' •••'••'•'•'• . . - .
. '•:..-'1:Л . ' - ' '., •.. •• •:' '...:procedure dfs ( v: вершина );varw. вершина;begin(1)marklv]:= visited;(2)for каждая вершина w из списка L[v] do(3)•.':•-.;''':::: :if mark[w] = unvisited then(4)dfs(w)end; { dfs }Анализ процедуры поиска в глубинуВсе вызовы процедуры dfs для полного обхода графа с п вершинами и е дугами,если е > п, требуют общего времени порядка О(е). Чтобы показать это, заметим, чтонет вершины, для которой процедура dfs вызывалась бы больше одного раза, поскольку рассматриваемая вершина помечается как visited в строке (1) (листинг 6.8)6.5. ОБХОД ОРИЕНТИРОВАННЫХ ГРАФОВ197•еще до следующего вызова процедуры dfs и никогда не вызывается для вершин,помеченных этой меткой.
Поэтому общее время выполнения строк (2) и (3) дляпросмотра всех списков смежности пропорционально сумме длин этих списков,т.е. имеет порядок О(е). Таким образом, предполагая, что е > п, общее время обхода по всем вершинам орграфа имеет порядок О(е), необходимое для"просмотра" всех дуг графа.Пример 6.13. Пусть процедура dfs применяется к ориентированному графу, представленному на рис. 6.16, начиная с вершины А. Алгоритм помечает эту вершинукак visited и выбирает вершину В из списка смежности вершины А.
Поскольку вершина В помечена как unvisited, обход графа продолжается вызовом процедурыdfs(B). Теперь процедура помечает вершину В как visitedin выбирает первую вершину из списка смежности вершины В. В зависимости от порядка представления вершин в списке смежности, следующей рассматриваемой вершиной может быть иливершина С, или вершина D.Предположим, что в списке смежности вершина С предшествует вершине D. Тогда осуществляется вызов dfs(C). В списке смежности вершины С присутствует только вершина А, но она уже посещалась ранее.
Поскольку все вершины в списке смежности вершины С исчерпаны, то поиск возвращается в вершину В, откуда процесспоиска продолжается вызовом процедуры dfs(D). Вершины А и С из списка смежности вершины D уже посещались ранее, поэтому поиск возвращается сначала в вершину В, а затем в вершину А.На этом первоначальный вызов dfs(A) завершен. Но орграф имеет вершины, которые еще не посещались: Е, F и G. Для продолжения обхода вершин графа выполняется вызов dfs(E). ПРис. 6.16. Ориентированный графГлубинный остовный лесВ процессе обхода ориентированного графа методом поиска в глубину только определенные дуги ведут к вершинам, которые ранее не посещались.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
