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

Эта формула устанавливает, что существует путь от верпшны i до верщины проходящий через верщины с номерами, не превыщающими к, только в следующих случаях.

1. Уже существует путь от верщины i до верщины /, который проходит через верщины с номерами, не превыщающими к - \.

2. Существует путь от верщины i до верщины к, проходящий через верщины с номерами, не превыщающими к - \, и путь от верщины к до верщины/, который также проходит через верщины с номерами, не превыщающими к - \.

Здесь, как и в алгоритме Флойда, kj = At lU. Щ nAilk.JJ = Ai i[k. JT. и вычисления можно выполнять в одной копии матрицы А. Программа WarshallBbvmc-ления транзитивного замыкания показана в листинге 6.7.

Листинг 6.7. Программа Warshall ДЛЯ вычисления транзитивного замыкания

procedure Warshall ( var А: array [1. . п, 1. . л] of boolean; С: аггау[1..л, 1..л] of boolean );

i, j, к: integer; begin

for i:= 1 to л do

for j:= 1 to л do

A[i, j] := C[i, j]; for k.:= 1 to л do

for i- 1 to л do

for j:= 1 to л do

if Afi, j] = false then

Afi, j]:= Ali, k] япАА(к, J]

end; { Warshall }

Нахождение центра ориентированного графа

Предположим, что необходимо найти центральную верщину в орграфе. Эту задачу также можно рещить с помощью алгоритма Флойда. Но сначала надо уточнить термин центральная вершина. Пусть v - произвольная верщина орграфа G = (V, Е). Эксцентриситет} верщины v определяется как

тах{минимальная длина пути от верщины w до верщины v)

Центром орграфа G называется верщина с минимальным эксцентриситетом. Другими словами, центром орграфа является верщина, для которой максимальное расстояние (длина пути) до других верщин минимально.

Пример 6.11. Рассмотрим помеченный орграф, показанный на рис. 6.14. В этом графе верщины имеют следующие эксцентриситеты.

Верщива Эксцентриситет

а ее

Из этой таблицы видно, что центром данного орграфа является верпшна d. □

В русской математической литературе наряду с термином "эксцентриситет" часто используется термин "максимальное удаление". - Прим. ред.



Найти центр орграфа сравнительно просто. Пусть С - матрица стоимостей для орграфа G.

1. Сначала применим процедуру Floyd (листинг 6.4) к матрице С для вычисления матрицы А, содержащей все кратчайшие пути орграфа G.

2. Находим максимальное значение в каждом столбце / матрицы А. Это значение равно эксцентриситету вершины /.

3. Находим вершину с минимальным эксцентриситетом. Она и будет центром графа G.


Рис. 6.14. Помеченный орграф

Время выполнения этого процесса определяется первым шагом, для которого время имеет порядок О(п). Второй шаг требует времени порядка О(п), а третий - 0(п).

Пример 6.12. Матрица всех кратчайших путей для орграфа из рис. 6.14 представлена на рис. 6.15. Максимальные значения в каждом столбце приведены под матрицей. D

Рис. 6.15. Матрица кратчайших путей

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

При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является так называемый поиск в глубину - обобщение метода обхода дерева в прямом порядке. Метод поиска в глубину составляет основу многих других эффективных алгоритмов работы с графами. В последних двух разделах этой главы представлены различные алгоритмы, основанные на методе поиска в глубину.



Предположим, что есть ориентированный граф G, в котором первоначально все вершины помечены меткой unvisited (не посещалась). Поиск в глубину начинается с выбора начальной вершины v графа G, для этой вершины метка unvisited меняется на метку visited (посещалась). Затем для каждой вершины, смежной с верщиной v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все верщины, которые можно достичь из вершины v, будут "удостоены" посещения, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа G.

Этот метод обхода вершин орграфа называется поиском в глубину, поскольку поиск не посещенных вершин идет в направлении вперед (вглубь) до тех пор, пока это возможно. Например, пусть х - последняя посещенная вершина. Для продолжения процесса выбирается какая-либо нерассмотренная дуга х -> у, выходящая из верщины x. Если верщина у уже посещалась, то ищется другая вершина, смежная с верщиной x. Если верщина у ранее не посещалась, то она помечается меткой visited и поиск начинается заново от вершины у. Пройдя все пути, которые начинаются в верщине у, возвращаемся в вершину х, т.е. в ту вершину, из которой впервые была достигнута вершина у. Затем продолжается выбор нерассмотренных дуг, исходящих из верщины x, и так до тех пор, пока не будут исчерпаны все эти дуги.

Для представления вершин, смежных с верщиной V, можно использовать список смежности L[v], а для определения вершин, которые ранее посещались, - массив mark (метка), чьи элементы будут принимать только два значения: visited и unvisited. Эскиз рекурсивной процедуры dfs (от depth-first search - поиск в глубину), реализующей метод поиска в глубину, представлен в листинге 6.8.

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

for v:= 1 to n do

mark[v]:= unvisited; for V. = 1 to л do

if inark[v] = unvisited then

dfs {v)

Отметим, что листинг 6.8 является только эскизом процедуры, который еще следует детализировать. Заметим также, что эта процедура изменяет только значения массива mark.

Листинг 6.8. Процедура поиска в глубину

procedure dfs ( v: вершина ); var

w: вершина; begin

(1) mark[v]:= visited;

(2) for каждая вершина w из списка L[v] do

(3) if mark[w] = unvisited then

(4) dfsiw) end; { dfs }

Анализ процедуры поиска в глубину

Все вызовы процедуры dfs для полного обхода графа с п верщинами и е дугами, если е > п, требуют общего времени порядка 0(e). Чтобы показать это, заметим, что нет верщины, для которой процедура dfs вызывалась бы больше одного раза, поскольку рассматриваемая вершина помечается как visited в строке (1) (листинг 6.8)





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.0037