Работа с графами Лекция 5

Графы Графы представляют собой распространенные структуры в информатике, и алгоритмы для работы с графами очень важны. Имеются сотни интересных вычислительных задач, сформулированных с использованием графов. При описании времени работы алгоритма над данным графом G = (V, Е) мы обычно определяем размер входного графа в терминах количества его вершин |V| и количества ребер |Е| графа, т.е. размер входных данных описывается двумя, а не одним параметром. 2

Для удобства и краткости в асимптотических обозначениях (таких, как О и θ-обозначения), и только в них, символ V будет означать |V|, а символ Е |Е|, т.е. когда мы будем говорить время работы алгоритма равно О(V Е) то это означает время работы алгоритма равно О (|V| |Е|). Еще одно соглашение принято для псевдокода. Мы обозначаем множество вершин графа G как V [G], а множество ребер как Е [G], т.е. в псевдокоде множества вершин и ребер рассматриваются как атрибуты графа. 3

Представление графов Имеется два стандартных способа представления графа G = (V, E): как набора списков смежных вершин или как матрицы смежности. Оба способа представления применимы как для ориентированных, так и для не ориентированных графов. Обычно более предпочтительно представление с помощью списков смежности, поскольку оно обеспечивает компактное представление разреженных (sparse) графов, т.е. таких, для которых |Е| гораздо меньше |V| 2. Представление при помощи матрицы смежности предпочтительнее в случае плотных (dense) графов, т.е. когда значение |Е| близко к |V| 2, или когда нам надо иметь возможность быстро определить, имеется ли ребро, соединяющие две данные вершины. 4

Представление графов 5

Представление графа G (V, Е) в виде списка смежности (adjacency-list representation) использует массив Adj из |V| списков, по одному для каждой вершины из V. Для каждой вершины и Є V список Adj [u] содержит все вершины v, такие что (и, v) Є Е, т.е. Adj [u] состоит из всех вершин, смежных с u в графе G ( СПИСОК может содержать и не сами вершины, а указатели на них). Вершины в каждом списке обычно хранятся в произвольном порядке. 6

Если G ориентированный граф, то сумма длин всех списков смежности равна |Е|, поскольку ребру (и, v) однозначно соответствует элемент v в списке Adj [u]. Если G не ориентированный граф, то сумма длин всех списков смежности равна 2|Е|, поскольку ребро (и, v), будучи не ориентированным, появляется в списке Adj [v] как и, и в списке Adj [u] как v. Как для ориентированных, так и для не ориентированных графов представление в виде списков требует объем памяти, равный θ (V + Е). Списки смежности легко адаптируются для представления взвешенных графов (weighted graph), т.е. графов, с каждым ребром которых связан определенный вес (weight), обычно определяемый весовой функцией (weight function) w : Е R. 7

Например, пусть G = (V, Е) взвешенный граф с весовой функцией w. Вес w (и, v) ребра (и, v) Є Е просто хранится вместе с вершиной v в списке смежности и. Представление с помощью списков смежности достаточно гибко в том смысле, что легко адаптируется для поддержки многих других вариантов графов. Потенциальный недостаток представления при помощи списков смежности заключается в том, что при этом нет более быстрого способа определить, имеется ли данное ребро (и, v) в графе, чем поиск v в списке Adj [u]. Этот недостаток можно устранить ценой использования асимптотически большего количества памяти и представления графа с помощью матрицы смежности. 8

Представление графа G = (V, Е) с помощью матрицы смежности (adjacency-matrix representation) предполагает, что вершины перенумерованы в некотором порядке числами 1,2,...,|V|. В таком случае представление графа G с использованием матрицы смежности представляет собой матрицу А = (а ij ) размером |V| х |V|, такую что 9 Поскольку граф не ориентирован, (и, v) и (v, и) представляют одно и то же ребро, так что матрица смежности не ориентированного графа совпадает с транспонированной матрицей смежности, т.е. А А Т. В ряде приложений это свойство позволяет хранить только элементы матрицы, находящиеся на главной диагонали и выше нее

Поиск в ширину Поиск в ширину (breadth-first search) представляет собой один из простейших алгоритмов для обхода графа и является основой для многих важных алгоритмов для работы с графами. Например, алгоритм Прима (Prim) поиска минимального остовного дерева или алгоритм Дейкстры (Dijkstra) поиска кратчайшего пути из одной вершины используют идеи, сходные с идеями, используемыми при поиске в ширину. 10

Пусть задан граф G = (V, Е) и выделена исходная (source) вершина s. Алгоритм поиска в ширину систематически обходит все ребра G для открытия всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество ребер) от s до каждой достижимой из s вершины. Кроме того, в процессе обхода строится дерево поиска в ширину с корнем s содержащее все достижимые вершины. Для каждой достижимой из s вершины v путь в дереве поиска в ширину соответствует кратчайшему (т.е. содержащему наименьшее количество ребер) пути от s до v в G. Алгоритм работает как для ориентированных, так и для не ориентированных графов. 11

Поиск в ширину имеет такое название потому, что в процессе обхода мы идем вширь, т.е. перед тем как приступить к поиску вершин на расстоянии к + 1, выполняется обход всех вершин на расстоянии к. Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. Изначально все вершины белые, и позже они могут стать серыми, а затем черными. Когда вершина открывается (discovered) в процессе поиска, она окрашивается. Таким образом, серые и черные вершины - это вершины, которые уже были открыты, но алгоритм поиска в ширину по- разному работает с ними, чтобы обеспечить объявленный порядок обхода. Если (и, v) Є Е и вершина u черного цвета, то вершина v либо серая, либо черная, т.е. все вершины, смежные с черной, уже открыты. Серые вершины могут иметь белых соседей, представляя собой границу между открытыми и неоткрытыми вершинами. 12

Поиск в ширину строит дерево поиска в ширину, которое изначально состоит из одного корня, которым является исходная вершина s. Если в процессе сканирования списка смежности уже открытой вершины и открывается белая вершина v, то вершина v и ребро (и, v) добавляются в дерево. Мы говорим, что и является предшественником (predecessor), или родителем (parent), v в дереве поиска вширь. Поскольку вершина может быть открыта не более одного раза, она имеет не более одного родителя. Взаимоотношения предков и потомков определяются в дереве поиска в ширину как обычно если и находится на пути от корня s к вершине v, то и является предком v, a v потомком и. 13

Процедура поиска в ширину Приведенная ниже процедура поиска в ширину BFS предполагает, что входной граф G = (V,E) представлен при помощи списков смежности. Кроме того, поддерживаются дополнительные структуры данных в каждой вершине графа. Цвет каждой вершины и Є V хранится в переменной color [u], а предшественник в переменной π [u]. Если предшественника у и нет (например, если и = s или и не открыта), то π[u] = nil. Расстояние от s до вершины и, вычисляемое алгоритмом, хранится в поле d[u]. Алгоритм использует очередь для работы с множеством серых вершин: 14

BFS(G, s) 1. for (для) каждой вершины u Є V[G] s 2. do color[u] WHITE 3. d[u] 4. π[u] NIL 5.color[s] GRAY 6.d[s] 0 7.π[s] NIL 8. Q 0 9.Enqueue(Q, S ) 10. while Q do u Dequeue (Q) 12. for (для) каждой v Є Adj[u] 13. do if color[v] = white 14. then color[v] GRAY 15. d[v] d[u] π[ V ] u 17. Enqueue(Q, V ) 18. color[u] BLACK 15 Внутри каждой вершины графа и приведено значение d[u], а состояние очереди Q показано на момент начала каждой итерации цикла while в строках Рядом с элементами очереди показаны расстояния до корня.

16

Процедура BFS работает следующим образом. В строках 1-4 все вершины, за исключением исходной вершины s, окрашиваются в белый цвет, для каждой вершины и полю d [u] присваивается значение, а в качестве родителя для каждой вершины устанавливается NIL. В строке 5 исходная вершина s окрашивается в серый цвет, поскольку она рассматривается как открытая в начале процедуры. В строке 6 ее полю d[s] присваивается значение 0, а в строке 7 ее родителем становится NIL. В строках 8-9 создается пустая очередь Q, в которую помещается один элемент s. Цикл while в строках выполняется до тех пор, пока остаются серые вершины (т.е. открытые, но списки смежности которых еще не просмотрены). При выполнении проверки в строке 10 очередь Q состоит из множества серых вершин. 17

Перед первой итерацией единственной серой вершиной и единственной вершиной в очереди Q, является исходная вершина s. В строке 11 определяется серая вершина и в голове очереди Q, которая затем удаляется из очереди. Цикл for в строках просматривает все вершины v в списке смежности и. Если вершина v белая, значит, она еще не открыта, и алгоритм открывает ее, выполняя строки Вершине назначается серый цвет, дистанция d [v] устанавливается равной d[u] + 1, а в качестве ее родителя указывается вершина и. После этого вершина помещается в хвост очереди Q. 18

После того как все вершины из списка смежности и просмотрены, вершине и присваивается черный цвет. Все вершины, которые окрашиваются в серый цвет (строка 14), вносятся в очередь (строка 17), а вершина, которая удаляется из очереди (строка 11), окрашивается в черный цвет (строка 18). Результат поиска в ширину может зависеть от порядка просмотра вершин, смежных с данной вершиной, в строке 12. Дерево поиска в ширину может варьироваться, но расстояния d, вычисленные алгоритмом, не зависят от порядка просмотра. 19

Анализ Перед тем как рассматривать различные свойства поиска в ширину, начнем с самого простого оценки времени работы алгоритма для входного графа G = (V,E). После инициализации ни одна вершина не окрашивается в белый цвет, поэтому проверка в строке 13 гарантирует, что каждая вершина вносится в очередь не более одного раза, а следовательно, и удаляется из очереди она не более одного раза. Операции внесения в очередь и удаления из нее требуют 0(1) времени, так что общее время операций с очередью составляет О (V). Поскольку каждый список смежности сканируется только при удалении соответствующей вершины из очереди, каждый список сканируется не более одного раза. Так как сумма длин всех списков смежности равна θ (Е), общее время, необходимое для сканирования списков, равно О (Е). Накладные расходы на инициализацию равны О (V), так что общее время работы процедуры BFS составляет О (V + Е). Таким образом, время поиска в ширину линейно зависит от размера представления графа G с использованием списков смежности. 20

Деревья поиска в ширину Процедура BFS строит в процессе обхода графа дерево поиска в ширину. Дерево представлено при помощи поля π в каждой вершине. Говоря более формально, для графа G = (V, Е) с исходной вершиной s мы определяем подграф предшествования (predecessor subgraph) графа G как G π = (V π, E π ), где V π = {v Є V : π [v] NIL} U {s} и E π = {(π[v], v) : v Є V π - {s}}. Подграф предшествования G π является деревом поиска в ширину (breadth-first tree), если V π состоит из вершин, достижимых из s, и для всех v Є V π, в G π, имеется единственный простой путь из s в v, такой что он одновременно является кратчайшим путем из s в v в G. 21

Приведенная далее процедура выводит все вершины на пути из s в v исходя из предположения, что дерево поиска в ширину уже построено процедурой BFS. Print_Path(G, s, v) 1. if v = s 2. then print s 3. else if π[v] = NIL 4. then print Путь из s в v отсутствует 5. else P RINT _P ATH (G, s, π[v]) 6. print v Время работы процедуры линейно зависит от количества выводимых вершин, так как каждый рекурсивный вызов процедуры осуществляется для пути, который на одну вершину короче текущего. 22

Поиск в глубину Стратегия поиска в глубину, как следует из ее названия, состоит в том, чтобы идти вглубь графа, насколько это возможно. При выполнении поиска в глубину исследуются все ребра, выходящие из вершины, открытой последней, и покидает вершину, только когда не остается неисследованных ребер при этом происходит возврат в вершину, из которой была открыта вершина v. Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины и поиск повторяется уже из нее. Этот процесс повторяется до тех пор, пока не будут открыты все вершины. 23

Как и в случае поиска в ширину, когда вершина v открывается в процессе сканирования списка смежности уже открытой вершины и, процедура поиска записывает это событие, устанавливая поле предшественника v π[v] равным и. В отличие от поиска в ширину, где подграф предшествования образует дерево, при поиске в глубину подграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершин. 24

Подграф предшествования (predecessor subgraph) поиска в глубину, таким образом, несколько отличается от такового для поиска в ширину. Определим его как граф G π = (V, Е π ), где Е π = {(π [v], v) : v Є V и π[v] NIL} Подграф предшествования поиска в глубин образует лес поиска в глубину (depth- first forest), который состоит из нескольких деревьев поиска в глубину (depth-first trees). Ребра в Е π называются ребрами дерева (tree edges). 25

Как и в процессе выполнения поиска в ширину, вершины графа раскрашиваются в разные цвета, свидетельствующие о их состоянии. Каждая вершина изначально белая, затем при открытии (discover) в процессе поиска она окрашивается в серый цвет, и по завершении (finish), когда ее список смежности полностью сканирован, она становится черной. Такая методика гарантирует, что каждая вершина в конечном счете находится только в одном дереве поиска в глубину, так что деревья не пересекаются. Помимо построения леса поиска в глубину, поиск в глубину также проставляет в вершинах метки времени (timestamp). Каждая вершина имеет две такие метки первую d [v], в которой указывается, когда вершина v открывается (и окрашивается в серый цвет), и вторая f[v], которая фиксирует момент, когда поиск завершает сканирование списка смежности вершины v и она становится черной. Эти метки используются многими алгоритмами и полезны при рассмотрении поведения поиска в глубину. 26

процедура DFS записывает в поле d [u] момент, когда вершина и открывается, а в поле f [u] момент завершения работы с вершиной и. Эти метки времени представляют собой целые числа в диапазоне от 1 до 2 |V|, поскольку для каждой из |V| вершин имеется только одно событие открытия и одно завершения. Для каждой вершины и d[u]<f [u]. До момента времени d [u] вершина имеет цвет WHITE, между d[u] и f [u] цвет GRAY, а после f [u] цвет BLACK. Далее представлен псевдокод алгоритма поиска в глубину. Входной граф G может быть как ориентированным, так и не ориентированным. Переменная time глобальная и используется нами для меток времени. 27

DFS(G) 1. for (Для) каждой вершины и Є V[G] 2. do color [и] WHITE 3. π[u] NIL 4. time О 5. for (Для) каждой вершины и Є V[G] 6. do if color[u] = white 7. then DFS_V ISIT ( U ) 28

DFS_V ISIT ( U ) 1.color[u] GRAY// Открыта белая вершина и 2. time time +1 3.d[u] time 4. for (Для) каждой вершины v Є Adj [и] //Исследование ребра (и, v). 5. do if color[v] = WHITE 6. then π[v] и 7. DFS_VlSIT(u) 8.color[u] BLACK// Завершение 9.f[u] time time +1 29

30

Ребра, исследованные алгоритмом, либо закрашены (если этот ребра деревьев), либо помечены пунктиром (в противном случае). Ребра, не являющиеся ребрами деревьев, помечены на рисунке буквами В (обратные back), F (прямые forward) и С (перекрестные cross). В вершинах указаны метки времени в формате открытие/завершение. В строках 1-3 все вершины окрашиваются в белый цвет, а их поля π инициализируются значением NIL. В строке 4 выполняется сброс глобального счетчика времени. В строках 5-7 поочередно проверяются все вершины из V, и когда обнаруживается белая вершина, она обрабатывается при помощи процедуры DFS_Visit. Каждый раз при вызове процедуры DFS_Visit(u) в строке 7, вершина и становится корнем нового дерева леса поиска в глубину. При возврате из процедуры DFS каждой вершине и сопоставляются два момента времени время открытия (discovery time) d [u] и время завершения (finishing time) f[u]. 31

При каждом вызове DFS_VISIT(u) вершина и изначально имеет белый цвет. В строке 1 она окрашивается в серый цвет, в строке 2 увеличивается глобальная переменная time, а в строке 3 выполняется запись нового значения переменной time в поле времени открытия d [u]. В строках 4-7 исследуются все вершины, смежные с и, и выполняется рекурсивное посещение белых вершин. При рассмотрении в строке 4 вершины v Є Adj [u], мы говорим, что ребро (u,v) исследуется (explored) поиском в глубину. И наконец, после того как будут исследованы все ребра, покидающие и, в строках 8-9 вершина и окрашивается в черный цвет, а в поле f [u] записывается время завершения работы с ней. 32

Заметим, что результат поиска в глубину может зависеть от порядка, в котором выполняется рассмотрение вершин в строке 5 процедуры DFS, а также от порядка посещения смежных вершин в строке 4 процедуры DFS_VISIT. На практике это обычно не вызывает каких-либо проблем, так как обычно эффективно использован может быть любой результат поиска в глубину, приводя по сути к одинаковым результатам работы алгоритма, опирающегося на поиск в глубину. Чему равно время работы процедуры DFS? Циклы в строках 1-3 и 5-7 процедуры DFS выполняются за время θ (V), исключая время, необходимое для вызова процедуры DFS_VISIT. Общая стоимость выполнения строк 4-7 процедуры DFS_VlSlT равна θ (Е). Время работы процедуры DFS, таким образом, равно θ (V + Е). 33

Топологическая сортировка Рассмотрим, каким образом можно использовать поиск в глубину для топологической сортировки ориентированного ациклического графа (directed acyclic graph, для которого иногда используется аббревиатура dag). Топологическая сортировка (topological sort) ориентированного ациклического графа G = = (V, Е) представляет собой такое линейное упорядочение всех его вершин, что если граф G содержит ребро (u,v), то и при таком упорядочении располагается до v (если граф не является ацикличным, такая сортировка невозможна). Топологическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо. 34

Ориентированные ациклические графы используются во многих приложениях для указания последовательности событий. На след. слайде приведен пример графа, построенного профессором Рассеянным для утреннего одевания. Некоторые вещи надо обязательно одевать раньше других, например, сначала носки, а затем туфли. Другие вещи могут быть одеты в произвольном порядке (например, носки и рубашка). Ребро (и, v) в ориентированном ациклическом графе на рис. а показывает, что вещь и должна быть одета раньше вещи v. Топологическая сортировка этого графа дает нам порядок одевания. На рис. б показан отсортированный ориентированный ациклический граф, вершины которого расположены вдоль горизонтальной линии так, что все ребра направлены слева направо. 35

На слайде видно, что топологически отсортированные вершины располагаются в порядке убывания времени завершения. 36

Простой алгоритм топологической сортировки ориентированного ациклического графа: T OPOLOGICAL _S ORT (G) 1. Вызов DFS(G) для вычисления времени завершения f[v] для каждой вершины v 2. По завершении работы над вершиной внести ее в начало связанного списка 3. return Связанный список вершин 37

Мы можем выполнить топологическую сортировку за время 0 (V + Е), поскольку поиск в глубину выполняется именно за это время, а вставка каждой из |V| вершин в начало связанного списка занимает время 0(1). 38