Файл: Программная инженерия, 18. 04. 2013. Красноярск сфу 2013 2.pdf

106
i, j, k: integer;
begin
for i := 1 to n do
for j
:= 1
to n do
A[i, j] := C[i, j];
for k: = 1 to n do
for i := 1 to n do
for j := 1 to n do
if A[i, j] = false then
A[i, j] := A[i, k] and A[k, j]
end; Нахождение центра ориентированного графа
Предположим, что необходимо найти центральную вершину в орграфе. Эту задачу также можно решить с помощью алгоритма Флойда. Однако сначала уточним термин центральная вершина. Пусть
v – произвольная вершина орграфа
G = (V, Е).Эксцентриситет или максимальное удаление вершины
v определяется как mах{минимальная длина пути от вершины
w до вершины v}
w
 V Центром орграфа G называется вершина с минимальным эксцентриситетом. Другими словами, центром орграфа является вершина, для которой максимальное расстояние (длина пути) до других вершин минимально. Рассмотрим помеченный орграф, показанный на рис. 5.14. В этом графе вершины имеют следующие эксцентриситеты: Вершина Эксцентриситет
a
∞
b
6
c
8
d
5
e
7 Найти центр орграфа сравнительно просто. Пусть С – матрица стои- мостей для орграфа
G.
1. Сначала применим алгоритм Флойда к матрице С для вычисления матрицы А, содержащей все кратчайшие пути орграфа G.
2. Находим максимальное значение в каждом столбце
i матрицы А Это значение равно эксцентриситету вершины
i.
3. Находим вершину с минимальным эксцентриситетом. Она и будет центром графа
G.

107 Время выполнения этого процесса определяется первым шагом, для которого время имеет порядок
O(n
3
). Второй шаг требует времени порядка па третий – п. Рис. 5.14. Помеченный граф Матрица всех кратчайших путей для орграфа, изображенного на рис.
5.14 представлена на рис. 5.15.
a b c d e
a
0 1 3 5 7
b
∞ 0 2 4 6
c
∞ 3 0 2 4
d
∞ 1 3 0 7
e
∞ 6 8 5 0 max
∞ 6 8 5 7 Рис. 5.15. Матрица кратчайших путей Максимальные значения в каждом столбце приведены под матрицей.
5.5. Обход ориентированных графов Для решения многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является так называемый поиск в глубину. Метод поискав глубину составляет основу многих других эффективных алгоритмов работы с графами. В последних двух разделах этой главы представлены различные алгоритмы, основанные на методе поискав глубину. Предположим, что есть ориентированный граф
G, в котором первоначально все вершины помечены меткой
unvisited (не посещалась. Поиск

108 в глубину начинается с выбора начальной вершины
v графа G, для этой вершины метка
unvisited меняется наметку (посещалась. Затем для каждой вершины, смежной с вершиной
v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все вершины, которые можно достичь из вершины
v, будут посещены, поиск заканчивается. Если некоторые вершины остались непосещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа
G. Этот метод обхода вершин орграфа называется поиском в глубину, поскольку поиск непосещенных вершин идет в направлении вперед вглубь) до тех пор, пока это возможно. Например, пусть х – последняя посещенная вершина. Для продолжения процесса выбирается какая-либо не- рассмотренная дугах у выходящая из вершины х Если вершина у уже посещалась, то ищется другая вершина, смежная с вершиной х Если вершина у ранее не посещалась, то она помечается меткой visited и поиск начинается заново от вершины у. Пройдя все пути, которые начинаются в вершине у возвращаемся в вершину х, те. в ту вершину, из которой впервые была достигнута вершина у. Затем продолжается выбор нерассмотрен- ных дуг, исходящих из вершины хи так до тех пор, пока не будут исчерпаны все эти дуги. Для представления вершин, смежных с вершиной
v, можно использовать список смежности
L[v], а для определения вершин, которые ранее посещались, – массив
mark (метка, чьи элементы будут принимать только два значения
visited и unvisited. Эскиз рекурсивной процедуры dfs (от
depth-first search – поиск в глубину, реализующей поиск в глубину, представлен в следующем листинге
procedure dfs (v: вершина
var
w: вершина
begin
(1)
mark[v] := visited;
(2)
for каждая вершина w из списка L[v] do
(3)
if mark[w] = unvisited then
(4)
dfs(w)
end; Чтобы применить эту процедуру к графу, состоящему из п вершин, надо сначала присвоить всем элементам массива
mark значение unvisited, затем начать поиск в глубину для каждой вершины, помеченной как
unvi-
sited. Описанное можно реализовать с помощью следующего кода

109
for v := 1 to n do
mark[v] := unvisited;
for v := 1 to n do
if mark[v] = unvisited then
dfs(v) Отметим, что листинг процедуры поискав глубину является только эскизом, который еще следует детализировать. Заметим также, что эта процедура изменяет только значения массива
mark. Анализ процедуры поискав глубину Все вызовы процедуры
dfs для полного обхода графа с п вершинами и е дугами, если е ≥ п, требуют общего времени порядка е. Чтобы показать это, заметим, что нет вершины, для которой процедура
dfs вызывалась бы больше одного раза, поскольку рассматриваемая вершина помечается как
visited в строке листинга (1) еще до следующего вызова процедуры dfs и никогда не вызывается для вершин, помеченных этой меткой. Поэтому общее время выполнения строки) для просмотра всех списков смежности пропорционально сумме длин этих списков, те. имеет порядок е. Таким образом, предполагая, что е ≥ п, общее время обхода по всем вершинам орграфа имеет порядок е, необходимое для просмотра всех дуг графа. Рассмотрим следующий пример. Пусть процедура
dfs применяется к ориентированному графу, представленному на рис. 5.16, начиная с вершины А Рис. 5.16. Ориентированный граф Алгоритм помечает эту вершину как
visited и выбирает вершину Виз списка смежности вершины А. Поскольку вершина В помечена как unvi-
sited, обход графа продолжается вызовом процедуры dfs(B). Теперь процедура помечает вершину В как visited и выбирает первую вершину из списка смежности вершины В. В зависимости от порядка представления вершин в списке смежности, следующей рассматриваемой вершиной может быть или вершина С, или вершина D. Предположим, что в списке смежности вершина С предшествует вершине
D. Тогда осуществляется вызов dfs(C). В списке смежности вершины С присутствует только вершина А, но она уже посещалась ранее. Поскольку все вершины в списке смежности вершины С исчерпаны, то поиск возвращается в вершину В, откуда процесс поиска продолжается вызовом процедуры
dfs(D). Вершины Аи Сиз списка смежности вершины D уже посещались ранее, поэтому поиск возвращается сначала в вершину В, а затем в вершину А. На этом первоначальный вызов
dfs(A) завершен. Но орграф имеет вершины, которые еще не посещались Е F и G. Для продолжения обхода вершин графа выполняется вызов
dfs(E). Глубинный остовный лес В процессе обхода ориентированного графа методом поискав глубину только определенные дуги ведут к вершинам, которые ранее не посещались. Такие дуги, ведущие к новым вершинам, называются дугами дерева и формируют для данного графа остовный лес, построенный методом поискав глубину, или, сокращенно, глубинный остовный лес. На рис. 5.17 показан глубинный остовный лес для графа из рис. 5.16. Здесь сплошными линиями обозначены дуги дерева. Отметим, что дуги дерева формируют именно лес, те. совокупность деревьев, поскольку методом поискав глубину к любой ранее не посещавшейся вершине можно придти только по одной дуге, а не по двум различным дугам. В добавление к дугам дерева существуют еще три типа дуг, определяемых в процессе обхода орграфа методом поискав глубину. Это обратные, прямые и поперечные дуги. Рис. 5.17. Глубинный остовной лес для орграфа, изображенного на рис 5.16 Обратные дуги (как дуга С → А на рис. 5.17) – это такие дуги, которые в остовном лесе идут от потомков к предкам. Отметим, что дуга из вершины в саму себя также является обратной дугой. Прямыми дугами называются дуги, идущие от предков к истинным потомкам, но которые не являются дугами дерева. На рис. 5.17 прямые дуги отсутствуют.

111 Дуги, такие как
D → C и G → D на рис. 5.17, соединяющие вершины, не являющиеся ни предками, ни потомками друг друга, называются поперечными дугами. Если при построении остовного дерева сыновья одной вершины располагаются слева направо в порядке их посещения и если новые деревья добавляются в лес также слева направо, то все поперечные дуги идут справа налево, что видно на рис. 5.17. Такое взаимное расположение вершин и деревьев выбрано неслучайно, так как это помогает формировать остовный лес. Как можно различить эти четыре типа дуг Легко определить дуги дерева, так как они получаются в процессе обхода графа как дуги, ведущие к тем вершинам, которые ранее не посещались. Предположим, что в процессе обхода орграфа его вершины нумеруются в порядке их посещения. Для этого в листинге процедуры поискав глубину после строки (1) надо добавить следующие строки
dfnumber[v] := count;
count := count + Назовем такую нумерацию глубинной нумерацией ориентированного графа. Всем потомкам вершины
v присваиваются глубинные номера, не меньшие, чем номер, присвоенный вершине
v. Фактически вершина w будет потомком вершины
v тогда и только тогда, когда выполняются неравенства количество потомков вершины
v
1
. Очевидно, что прямые дуги идут от вершин с низкими номерами к вершинам с более высокими номерами, а обратные дуги – от вершин с высокими номерами к вершинам с более низкими номерами. Все поперечные дуги также идут от вершин с высокими номерами к вершинам с более низкими номерами. Чтобы показать это, предположим, что есть дугах у и выполняется неравенство dfnumber(x)≤ dfnumber(y). Отсюда следует, что вершинах пройдена (посещена) раньше вершины у. Каждая вершина, пройденная в промежуток времени от вызова
dfs(x) и до завершения
dfs(y), становится потомком вершины х в глубинном остовном лесу. Если при рассмотрении дуги х → у вершина у еще не посещалась, то эта дуга становится дугой дерева. В противном случае дугах убудет прямой дугой. Таким образом, если для дуги х → у выполняется неравенство, то она не может быть поперечной дугой. Далее будет рассмотрено применение метода поискав глубину для решения различных задач на графах.
1
Для истинных потомков вершины v первое из приведенных неравенств должно быть строгим.

112
5.6. Ориентированные ациклические графы Ориентированный ациклический граф – это орграф, не имеющий циклов. Можно сказать, что ациклический орграф более общая структура, чем дерево, но менее общая по сравнению с обычным ориентированным графом. На рис. 5.18 представлены дерево, ациклический орграф и ориентированный граф с циклом. Рис. 5.18. Три ориентированных графа Ациклические ориентированные графы удобны для представления синтаксических структур арифметических выражений, имеющих повторяющиеся подвыражения. Например, на рис. 5.19 показан ациклический орграф для выражения аса+ ее. Подвыражения аи (ас встречаются в выражении несколько раз, поэтому они представлены вершинами, в которые входят несколько дуг. Рис. 5.19. Ориентированный ациклический граф для арифметического выражения Ациклические орграфы также полезны для представления отношений частичных порядков. Отношением частичного порядка
R, определенным на множестве
S, называется бинарное отношение, для которого выполняются следующие условия

113 1. Ни для какого элемента а из множества S не выполняется aRa свойство антирефлексивности).
2. Для любых ас из S, таких, что аи, выполняется ас свойство транзитивности. Двумя естественными примерами отношений частичного порядка могут служить отношение меньше чем (обозначается знаком «<»), заданное на множестве целых чисел, и отношение строгого включения (
) множеств. Например, пусть
S = {1, 2, 3} и P(S) – множество всех подмножеств множества
S, те. Отношение строгого включения (
) является отношением частичного порядка на множестве
P(S). Очевидно, включение А
 Ане выполняется для любого множества А из Р (антирефлексивность), и при выполнении А
 В и В
 С выполняется АС (транзитивность. Ациклические орграфы можно использовать для графического изображения отношения частичного порядка между какими-либо объектами. Для начала можно представить отношение
R как одноименное множество пар (дуг) таких, что пара (а, b) принадлежит этому множеству только тогда, когда выполняется
aRb. Если отношение R определено на множестве элементов
S, то ориентированный граф G = (S, R) будет ациклическим. И наоборот, пусть
G = (S, R) является ациклическим орграфом, а R
+
– отношение, определенное следующим образом
aR
+
b выполняется тогда и только тогда, когда существует путь (длиной не менее 1) от вершины а к вершине. Тогда R
+
– отношение частичного порядка на
S. (Отношение R
+
является транзитивным замыканием отношения
R.) Рис. 5.20. Ациклический граф, представляющий отношение строгого включения В качестве примера на рис. 5.20 показан ациклический орграф (
P(S),
R), где S = {1, 2, 3}. Здесь R
+
– отношение строгого включения на множестве Проверка ацикличности орграфа Предположим, что есть ориентированный граф
G = (V, Е. Необходимо определить, является ли он ациклическим, те. имеет ли он циклы. Чтобы ответить на этот вопрос, можно использовать метод поискав глубину. Если при обходе орграфа
G методом поискав глубину встретится обратная дуга, то ясно, что граф имеет цикл. С другой стороны, если в орграфе есть цикл, тогда обратная дуга обязательно встретится при обходе этого орграфа методом поискав глубину. Чтобы доказать это, предположим, что орграф имеет цикл (рис. 5.21). Пусть при обходе данного орграфа методом поискав глубину вершина
v имеет наименьшее глубинное число среди всех вершин, составляющих цикл. Рассмотрим дугу
u → v, принадлежащую этому циклу. Поскольку вершина
u входит в цикл, то она должна быть потомком вершины
v в Рис. 5.21. Ациклический орграф, представляющий структуру предшествова- ний глубинном остовном лесу. Поэтому дуга
u → v не может быть поперечной дугой. Так как глубинный номер вершины
u больше глубинного номера вершины
v, то отсюда следует, что эта дуга не может быть дугой дерева и прямой дугой. Следовательно, дуга
u → v является обратной дугой, как показано на рис. 5.21. Топологическая сортировка Большие проекты часто разбиваются на совокупность меньших задач, которые выполняются в определенном порядке и обеспечивают полное завершение целого проекта. Например, план учебного заведения требует определенной последовательности в чтении учебных курсов. Ациклические орграфы могут служить естественной моделью для таких ситуаций. Например, когда чтение учебного курса С предшествует чтению учебного курса
D, создается дуга от курса С к курсу
D. Чтобы проиллюстрировать этот пример приведем ациклический орграф (рис.
5.22), представляющий структуру предше- ствований пяти учебных курсов. Чтение учебного курса С, например, требует предварительного чтения курсов Си С. Рис. 5.22. Ациклический орграф, представляющий структуру предшествований
Топологическая сортировка – это процесс линейного упорядочива- ния вершин ациклического орграфа таким образом, что если существует

115 дуга от вершины
i к вершине j, тов упорядоченном списке вершин орграфа вершина
i предшествует вершине j. Например, для орграфа из рис. 5.22 вершины после топологической сортировки расположатся в следующем порядке С, С, С, С, С. Топологическую сортировку легко выполнить с помощью модифицированной процедуры поискав глубину, если в ней после строки (4) добавить оператор вывода на печать
procedure topsort (v: вершина печать в обратном топологическом порядке вершин, достижимых из вершины v}
w: вершина
begin
mark[v] := visited;
for каждая вершина w из списка L[v] do
if mark[w] = unvisited then
topsort (w);
writeln (v)
end; Когда процедура
topsort заканчивает поиск всех вершин, являющихся потомками вершины
v, печатается сама вершина v. Отсюда следует, что процедура
topsort распечатывает все вершины в обратном топологическом порядке. Эта процедура работает вследствие того, что в ациклическом орграфе нет обратных дуг. Рассмотрим, что происходит, когда поиск в глубину достигает конечной вершины х. Из любой вершины могут исходить только дуги дерева, прямые и поперечные дуги. Но все эти дуги направлены в вершины, которые уже пройдены (посещались до достижения вершины хи поэтому предшествуют вершине х.