Главная Промышленная автоматика. Эта формула устанавливает, что существует путь от верпшны 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.0019 |