Алгоритмы на графах

Алгоритмы на графах План: 1. Алгоритм Дейкстры 2. Транзитивное замыкание (алгоритм Уоршела) 3. Нахождение центра орграфа 4. Обход орграфов 1. Алгоритм Дейкстры В этом разделе мы рассмотрим задачи нахождения путей в ориентированном графе. Пусть есть ориентированный граф G – (V, Е), у которого все дуги имеют неотрицательные метки (стоимости дуг), а одна вершина определена как источник. Задача состоит в нахождении стоимости кратчайших путей от источника ко всем другим вершинам графа G (здесь длина пути определяется как сумма стоимостей дуг, составляющих путь). Эта задача часто называется задачей нахождения кратчайшего пути с одним источником. Отметим, что мы будем говорить о длине пути даже тогда, когда она измеряется в других, не линейных, единицах измерения, например во временных единицах. Может показаться, что более естественной задачей будет нахождение кратчайшего пути от источника к определенной вершине назначения. Но эта задача в общем случае имеет такой же уровень сложности, что и задача нахождения кратчайшего пути для всех вершин графа (за исключением того "счастливого" случая, когда путь к вершине назначения будет найден ранее, чем просмотрены пути ко всем вершинам графа). Для решения поставленной задачи будем использовать "жадный" алгоритм, который часто называют алгоритмом Дейкстры (Dijkstra). Алгоритм строит множество S вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной вершине проходит только через вершины множества S. Назовем такой путь особым. На каждом шаге алгоритма используется также массив D, в который записываются длины кратчайших особых путей для каждой вершины. Когда множество S будет содержать все вершины орграфа, т.е. для всех вершин будут найдены "особые" пути, тогда массив D будет содержать длины кратчайших путей от источника к каждой вершине. Алгоритм Дейкстры представлен в листинге 1. Здесь предполагается, что в орграфе G вершины поименованы целыми числами, т.е. множество вершин V = {1, 2, ..., n}, причем вершина 1 является источником. Массив С – это двумерный массив стоимостей, где элемент C[i, j] равен стоимости дуги i  j. Если дуги i  j не существует, то C[i, j] ложится равным ∞, т.е. большим любой фактической стоимости дуг. На каждом шаге D[i] содержит длину текущего кратчайшего особого пути к вершине i. Листинг 1. Алгоритм Дейкстры procedure Dijkstra; begin 1) S:= {1}; 2) for i:= 2 to n do 3) D[i]:= C[1, i] ; { инициализация D } 4) for i:= 1 to n - 1 do begin 5) выбор из множества V\S такой вершины w, что значение D[w] минимально; 6) добавить w к множеству S; 7) for каждая вершина v из множества V\S do 8) D[v]:= min(D[v], D[w] + C[w, v] ) end end; Пример 1. Применим алгоритм Дейкстры для ориентированного графа, показанного на рис. 1. Вначале S = {1}, D[2] = 10, D[3] = ∞, D[4] = 30 и D[5] = 100. На первом шаге цикла (строки 4 - 8 листинга 1) w = 2, т.е. вершина 2 имеет минимальное значение в массиве D. Затем вычисляем D[3] = min(∞, 10 + 50) = 60. D[4] и D[5] не изменяются, так как не существует дуг, исходящих из вершины 2 и ведущих к вершинам 4 и 5. рис. 1 Несложно внести изменения в алгоритм так, чтобы можно было определить сам кратчайший путь (т.е. последовательность вершин) для любой вершины. Для этого надо ввести еще один массив Р вершин, где P[v] содержит вершину, непосредственно предшествующую вершине v в кратчайшем пути. Вначале положим P[v] = 1 для всех v≠1. В листинге 1 после строки (8) надо записать условный оператор с условием D[w] + C[w, v] < D[v], при выполнении которого элементу P[v] присваивается значение w. После выполнения алгоритма кратчайший путь к каждой вершине можно найти с помощью обратного прохождения по предшествующим вершинам массива Р. Для орграфа из примера 1 массив Р имеет следующие значения: Р[2] = 1, Р[3] = 4, Р[4] = 1, Р[5] = 3. Для определения кратчайшего пути, например от вершины 1 к вершине 5, надо отследить в обратном порядке предшествующие вершины, начиная с вершины 5. На основании значений массива Р определяем, что вершине 5 предшествует вершина 3, вершине 3 — вершина 4, а ей, в свою очередь, — вершина 1. Таким образом, кратчайший путь из вершины 1 в вершину 5 составляет следующая последовательность вершин: 1, 4, 3, 5. 2. Транзитивное замыкание (алгоритм Уоршела) Во многих задачах интерес представляет только сам факт существования пути, длиной не меньше единицы, от вершины i до вершины j. Алгоритм Флойда можно приспособить для решения таких задач. Но полученный в результате алгоритм еще до Флойда разработал Уоршелл (S. Warshall), поэтому мы будем называть его алгоритмом Уоршелла. Предположим, что матрица стоимостей С совпадает с матрицей смежности для данного орграфа G, т.е. C[i, j] = 1 только в том случае, если есть дуга i  j, и C[i, j] = 0, если такой дуги не существует. Мы хотим вычислить матрицу А такую, что A[i, j]=1 тогда и только тогда, когда существует путь от вершины i до вершины j длиной не менее 1 и A[i, j] = 0 — в противном случае. Такую матрицу А часто называют транзитивным замыканием матрицы смежности. Транзитивное замыкание можно вычислить с помощью процедуры, подобной Floyd, применяя на k-м шаге следующую формулу к булевой матрице А: Ak[i, j] = Ak-1[i, j] or (Ak-1[i, k] and Ak-1[k, j]) procedure Marshall ( var A: array[l..n, l..n] of boolean; C: array[l..n, l..n] of boolean ); var i, j, к: 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; 3. Нахождение центра орграфа Предположим, что необходимо найти центральную вершину в орграфе. Эту задачу также можно решить с помощью алгоритма Флойда. Но сначала надо уточнить термин центральная вершина. Пусть v — произвольная вершина орграфа G = (V, Е). Эксцентриситет вершины v определяется как mах{минимальная длина пути от вершины w до вершины v}  wV Центром орграфа G называется вершина с минимальным эксцентриситетом. Другими словами, центром орграфа является вершина, для которой максимальное расстояние (длина пути) до других вершин минимально. Рассмотрим помеченный орграф, показанный на рис. 2. В этом графе вершины имеют следующие эксцентриситеты. Вершина Эксцентриситет а ∞ b 6 с 8 d 5 е 7 Из этой таблицы видно, что центром данного орграфа является вершина d. Рис 2 Пусть С — матрица стоимостей для орграфа G. 1. Сначала применим процедуру Floyd к матрице С для вычисления матрицы А, содержащей все кратчайшие пути орграфа G. 2. Находим максимальное значение в каждом столбце i матрицы А. Это значение равно эксцентриситету вершины i. 3. Находим вершину с минимальным эксцентриситетом. Она и будет центром графа G. Рис 3 Матрица кратчайших путей 1. Обход орграфов При решении многих задач, касающихся ориентированных графов, необходим эффективный метод систематического обхода вершин и дуг орграфов. Таким методом является так называемый поиск в глубину – обобщение метода обхода дерева в прямом порядке. Метод поиска в глубину составляет основу многих других эффективных алгоритмов работы с графами. Предположим, что есть ориентированный граф G, в котором первоначально все вершины помечены меткой unvisited (не посещалась). Поиск в глубину начинается с выбора начальной вершины v графа G, для этой вершины метка unvisited меняется на метку visited (посещалась). Затем для каждой вершины, смежной с вершиной v и которая не посещалась ранее, рекурсивно применяется поиск в глубину. Когда все вершины, которые можно достичь из вершины v, будут "удостоены" посещения, поиск заканчивается. Если некоторые вершины остались не посещенными, то выбирается одна из них и поиск повторяется. Этот процесс продолжается до тех пор, пока обходом не будут охвачены все вершины орграфа G. Этот метод обхода вершин орграфа называется поиском в глубину, поскольку поиск не посещенных вершин идет в направлении вперед (вглубь) до тех пор, пока это возможно. Например, пусть х – последняя посещенная вершина. Для продолжения процесса выбирается какая-либо нерассмотренная дуга х  у, выходящая из вершины х. Если вершина у уже посещалась, то ищется другая вершина, смежная с вершиной х. Если вершина у ранее не посещалась, то она помечается меткой visited и поиск начинается заново от вершины у. Пройдя все пути, которые начинаются в вершине у, возвращаемся в вершину х, т.е. в ту вершину, из которой впервые была достигнута вершина у. Затем продолжается выбор нерассмотренных дуг, исходящих из вершины х, и так до тех пор, пока не будут исчерпаны все эти дуги. Для представления вершин, смежных с вершиной v, можно использовать список смежности L[v], а для определения вершин, которые ранее посещались, – массив mark (метка), чьи элементы будут принимать только два значения: visited и unvisited. Эскиз рекурсивной процедуры dfs (от depth-first search – поиск в глубину), реализующей метод поиска в глубину, представлен в листинге 2. Чтобы применить эту процедуру к графу, состоящему из n вершин, надо сначала присвоить всем элементам массива mark значение unvisited, затем начать поиск в глубину для каждой вершины, помеченной как unvisited. Описанное можно реализовать с помощью следующего кода: for v:= 1 to n do mark[v]:= unvisited; for v:= 1 to n do if mark[v] = unvisited then dfs (v) Отметим, что листинг 2 является только эскизом процедуры, который еще следует детализировать. Заметим также, что эта процедура изменяет только значения массива mark. Листинг 2. Процедура поиска в глубину 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; Пусть процедура dfs применяется к ориентированному графу, представленному на рис. 4, начиная с вершины А. Алгоритм помечает эту вершину как visited и выбирает вершину В из списка смежности вершины А. Поскольку вершина В помечена как unvisited, обход графа продолжается вызовом процедуры dfs(B). Теперь процедура помечает вершину В как visited и выбирает первую вершину из списка смежности вершины В. В зависимости от порядка представления вершин в списке смежности, следующей рассматриваемой вершиной может быть или вершина С, или вершина D. Рис. 4 Предположим, что в списке смежности вершина С предшествует вершине D. Тогда осуществляется вызов dfs(C). В списке смежности вершины С присутствует только вершина А, но она уже посещалась ранее. Поскольку все вершины в списке смежности вершины С исчерпаны, то поиск возвращается в вершину В, откуда процесс поиска продолжается вызовом процедуры dfs(D). Вершины Л и С из списка смежности вершины D уже посещались ранее, поэтому поиск возвращается сначала в вершину В, а затем в вершину А. На этом первоначальный вызов dfs(A) завершен. Но орграф имеет вершины, которые еще не посещались: Е, F и G. Для продолжения обхода вершин графа выполняется вызов dfs(E).