34. Поиски в глубину и в ширину для неориентированного и ориентированного графа. Временная сложность алгоритмов. Выделение связных компонент в графе

 

Поиск в глубину

 для ориентированного графа.

Рассматривая поиск в глубину, удобно представлять себе ориентированный граф как образ дерева. Более точно, пусть есть ориентированный граф, одна из вершин которого выделена. Будем предполагать, что все вершины доступны из выделенной по ориентированным путям. Построим дерево, которое можно было бы назвать "универсальным накрытием" нашего графа. Его корнем будет выделенная вершина графа. Из корня выходят те же стрелки, что и в графе - их концы будут сыновьями корня. Из них в дереве выходят те же стрелки, что и в графе и так далее. Разница между графом и деревом в том, что пути в графе, ведущие в одну и ту же вершину, в дереве "расклеены". В других терминах: вершина дерева - это путь в графе, выходящий из корня. Ее сыновья - это пути, продолженные на одно ребро. Заметим, что дерево бесконечно, если в графе есть ориентированные циклы.

Имеется естественное отображение дерева в граф (вершин в вершины). При этом каждая вершина графа имеет столько прообразов, сколько путей в нее ведет. Поэтому обход дерева (посещение его вершин в том или ином порядке) одновременно является и обходом графа - только каждая вершина посещается многократно.

Будем предполагать, что для каждой вершины графа выходящие из неё ребра упорядочены (например, пронумерованы). Тем самым для каждой вершины дерева выходящие из неё ребра также упорядочены. Будем обходить дерево так: сначала корень, а потом поддеревья (в порядке ведущих в них ребер). Такой обход дерева рассматривался нами в главе о рекурсии. Ему соответствует обход графа. Если выкинуть из этого обхода повторные посещения уже посещенных вершин, то получится то, что называется "поиск в глубину".

Другими словами, на путях, выходящих из выделенной вершины, введем порядок: путь предшествует своему продолжению; если два пути расходятся в некоторой вершине, то меньшим считается тот, который выходит из нее по меньшему ребру. Вершины теперь упорядочиваются в соответствии с минимальными путями, в них ведущими. Обход вершин графа в указанном порядке называется поиском в глубину.

для неориентированного графа

Алгоритм поиска в глубину для ориентированного графа можно использовать для обхода вершин и неориентированных графов, поскольку неориентированное ребро (v, w) можно пред­ставить в виде пары ориентированных дуг v  w и w  v.

Фактически построить глyбинный остовный лес для неориентированного графа (т.е. совершить обход его вершин) даже проще, чем для ориентированного. Во-первых, заме­тим, что каждое дерево остовного леса соответствует одной связной компоненте исход­ного графа, поэтому, если граф связный, его глубинный остовный лес будет состоять только из одного дерева. Во-вторых, при построении остовного леса для орграфа мы различали четыре типа дуг: дуги дерева, передние, обратные и поперечные дуги, а для неориентированного графа в этой ситуации выделяют только два типа ребер: ребра де­рева и обратные ребра. Так как для неориентированного графа не существует направ­ления ребер, то, естественно, прямые и обратные ребра здесь не различаются и объеди­нены общим названием обратные ребра. Аналогично, так как в остовном дереве для неориентированного графа вершины не делятся на потомков и предков, то нет и пере­крестных ребер. В самом деле, пусть есть ребро (v, w) и предположим, что при обходе графа вершина v достигнута раньше, чем вершина w. Тогда процедура dfs(v) не может закончиться раньше, чем будет рассмотрена вершина w. Поэтому в остовном дереве вершину w можно считать потомком вершины v. Но подобным образом, если сначала вызывается dfs(w), вершина и становится потомком вершины w.

Итак, при обходе вершин неориентированного графа методом поиска в глубину все ребра делятся на следующие группы.

1.    Ребра дерева — это такие ребра (v, w), что при обходе графа процедура dfs(v) вы­зывается непосредственно перед процедурой dfs(w) или, наоборот, сначала вызы­вается процедура dfs(w), а затем сразу процедура dfs(v).

2.    Обратные ребра — такие ребра (v, w), что ни процедура dfa(w) не следует непо­средственно за процедурой dfs(v), ни процедура dfs(v) не следует непосредственно за процедурой dfs(w) (т.е. между вызовами этих процедур следуют вызовы не­скольких других процедур dfs(x))

 

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.

Алгоритм поиска в глубину

Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:

Из множества всех белых вершин выберем любую вершину, обозначим её v1.

  1. Выполняем для нее процедуру DFS(v1).
  2. Перекрашиваем ее в черный цвет.
  3. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.
  4. Процедура DFS (параметр — вершина u \in V)
  5. Перекрашиваем вершину u в серый цвет.
  6. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:
  7. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).
  8. Окрашиваем w в черный цвет.

 

Поиск в ширину

Другой метод систематического обхода вершин графа называется поиском в ширину. Он получил cвоe название из-за того, что при достижении во время обхода любой вершины v далее рассматриваются все вершины, смежные с вершиной v, т.е. осуществляется просмотр вершин "в ширину". Этот метод также можно применить и к ориентированным графам.

Так же, как и при применении поиска вглубь, посредством метода поиска в ширину при обходе графа создается остовный лес. Если после достижения вершины х при рассмотрении ребра (x,y) вершина у не посещалась ранее, то это ребро считается ребром дерева. Если же вершина у уже посещалась ранее, то ребро (х, у) будет поперечным ребром, так как оно соединяет вершины, не связанные наследованием друг друга.

В эскизе процедуры bfs, реализующей алгоритм поиска в ширину, ребра дерева помещаются в первоначально пустой массив Т, формирующий остовный лес. Посещенные вершины графа заносятся в очередь Q. Массив mark (метка) отслеживает состояние вершин: если вершина v пройдена, то элемент mark[v] принимает значение visited (посещалась), первоначально все элементы этого массива имеют значение unvisited (не посещалась). Отметим, что в этом алгоритме во избежание по-вторного помещения вершины в очередь пройденная вершина помечается как visited до помещения ее в очередь. Процедура bfs работает на одной связной компоненте, если граф не односвязный, то эта процедура должна вызываться для вершин каждой связной компоненты.

 

Если граф имеет п вершин и е ребер, а также если для представления ребер используются списки смежности, общее время обхода такого графа составит О(max(n, е)). Поскольку обычно e > n, то получаем вре­мя выполнения алгоритма поиска в ширину порядка О(e), т.е. такое же, как и для алгоритма поиска в глубину.

 

 

 

Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т. д.

Реализация  

Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы.

Выделение связных компонент

 

Точкой сочленения графа называется такая вершина v, когда при удалении этой вершины и всех ребер, инцидентных вершине v, связная компонента графа разбивается на две или несколько частей. Например, точками сочленения для графа из рис. являются вершины а и с. Если удалить вершину а, то граф, который является одной связной компонентой, разбивается на два "треугольника {b, d, е} и {с, f, g}. Если удалить вершину c, тo граф расчленяется на подграфы {а, b, d, е} и {f, g}. Но если удалить какую-либо дру­гую вершину, то в этом случае не удастся разбить связную компоненту на несколько час­тей. Связный граф, не имеющий точек сочленения, называется двусвязным. Для нахож­дения двусвязных компонент графа часто используется метод поиска в глубину.

Метод нахождения точек сочленения часто применяется для решения важной проблемы, касающейся k-связности графов. Граф называется k-связным, если удаление любых k - 1 вершин не приведет к расчленению графа(Существует другое, более конструктивное определение k-связности. Граф называется k связным, если между любой парой вершин v и w существует не менее k разных путей, таких, что, за исключением вершин v и w, ни одна из вершин, входящих в один путь, не входит ни в какой другой из этих путей.). В частности, граф имеет связность 2 или выше тогда и только тогда, когда он не имеет точек сочленения, т.е. только тогда, когда он является двусвязным. Чем выше связность графа, тем больше можно удалить вершин из этого графа, не нарушая его целостности, т.е. не разбивая его на отдельные компоненты.

Опишем простой алгоритм нахождения всех точек сочленения связного графа, основанный на методе поиска в глубину. При отсутствии этих точек граф, естественно, будет двусвязным, т.е. этот алгоритм можно рассматривать так же, как тест на двусвязность неориентированного графа.

1.    Выполняется обход графа методом поиска в глубину, при этом для всех вершин v вычисляются числа dfnumber[v], введенные в разделе 6.5. В сущности, эти числа фиксируют последовательность обхода вершин в прямом порядке вершин глубинного остовного дерева.

2.    Для каждой вершины v вычисляется число low[v], равное минимуму чисел dfnumber потомков вершины v, включая и саму вершину v, и предков w вершины v, для которых существует обратное ребро (х, w), где х — потомок вершины v. Числа low[v] для всех вершин v вычисляются при обходе остовного дерева в обратном порядке, поэтому при вычислении low[v] для вершины v уже подсчитаны числа low[x] для всех потомков х вершины v. Следовательно, low[v] вычисляется как минимум следующих чисел:

а) dfnumber[v];

б) dfnumber[z] всех вершин z, для которых существует обратное ребро (v, z);

в) low[x] всех потомков х вершины v.

3.    Теперь точки сочленения определяются следующим образом:

а) корень остовного дерева будет точкой сочленения тогда и только тогда, когда он имеет двух или более сыновей. Так как в остовном дереве, которое получе но методом поиска вглубь, нет поперечных ребер, то удаление такого корня расчленит остовное дерево на отдельные поддеревья с корнями, являющимися сыновьями корня построенного остовного дерева;

б) вершина v, отличная от корня, будет точкой сочленения тогда и только тогда, когда имеет такого сына w, что low[w]  dfnurnber[v]. В этом случае удаление вершины v (и, конечно, всех инцидентных ей ребер) отделит вершину w и всех ее потомков от остальной чисти графа. Цели же low[w] < dfnumber[v], то существует путь по ребрам дерева к потомкам вершины w и обратное ребро от какого-нибудь из этих потомков к истинному предку вершины v (именно значению dfnumber для этого предка равно low[w]). Поэтому в данном случае удаление вершины v не отделит от графа поддерево с корнем w.