Главная Промышленная автоматика.

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

Листинг 7.4. Алгоритм поиска в ширину

procedure bfs ( v ) ;

{ bfs обходит все вершины, достижимые из вершины v } var

Q: QUEUE { очередь для вершин } к, у: вершина; begin

mark[v] := visited; ENQUEUE (v, Q);

while not empty (0) do begin

x:= front(O) ; DEQUEUE(Q);

for для каждой вершины у, смежной с вершиной х do if mark [у] = unvi si ted tlien begin mark[y]:= visited; ENQUEUE (y, Q) ; INSERT ( (x, y) , T)

end end; { bfs }

Пример 7.7. Остовное дерево для графа из рис. 7.8,а, построенное методом поиска в ширину, показано на рис. 7.9. Здесь обход графа начат с вершины а. Как и ранее, ребра дерева показаны сплошными линиями, а другие ребра - пунктирными. Отметим также, что дерево нарисовано от корня, а все сыновья любой вершины располагаются слева направо в порядке посешения их. Р


Рис. 7.9. Остовное дерево для графа из рис. 7.S,a, полученное методом поиска в ширину

Время выполнения алгоритма поиска в ширину такое же, как и для алгоритма поиска в глубину. Каждая пройденная вершина помешается в очередь только один раз, поэтому количество выполнений цикла while совпадает с количеством просмотренных вершин. Каждое ребро (х, у) просматривается дважды, один раз для вершины X и один раз для вершины у. Поэтому, если граф имеет п вершин и е ребер, а также если для представления ребер используются списки смежности, обшее время обхода такого графа составит 0(тах(п, е)). Поскольку обычно е > «, то получаем время выполнения алгоритма поиска в ширину порядка 0(e), т.е. такое же, как и для алгоритма поиска в глубину.



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

Метод поиска в пгирину можно использовать для обнаружения циклов в произвольном графе, причем за время 0(л) (п - количество вершин графа), которое не зависит от количества ребер. Как показано в разделе 7.1, граф с п вершинами и с п или большим количеством ребер обязательно имеет цикл. Однако если в графе п - 1 или меньше ребер, то цикл может быть только в том случае, когда граф состоит из двух или более связных компонент. Один из способов наховдения циклов состоит в построении остовного леса методом поиска в ширину. Тогда каждое поперечное ребро (v, w) замыкает простой цикл, состояший из ребер дерева, ведущих к вершинам v и W от общего предка этих вершин, как показано на рис. 7.10.

Корень

/ у 1------------/ IV j

Рис. 7.10. Цикл, найденный методом поиска в ширину

7.4. Точки сочленения и двусвязные компоненты

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

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

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



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

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

2. Для каждой вершины v вычисляется число iou>[u], равное минимуму чисел dfnumbemoTOMKOB вершины v, включая и саму вершину v, и предков w вершины V, для которых сушествует обратное ребро (х. w), где х - потомок вершины V. Числа ;ош[1;]для всех вершин v вычисляются при обходе остовного дерева в обратном порядке, поэтому при вычислении <ош[и]для вергпины v уже подсчитаны числа ;ош[ж]для всех потомков х вершины г. Следовательно, loid[u] вычисляется как минимум следующих чисел:

а) dfnumber[v];

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

в) 1ои)[х]ъсех потомков х вершины г.

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

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

б) вершина г, отличная от корня, будет точкой сочленения тогда и только тогда, когда имеет такого сына w, что loiv[w] > dfnumber[u].B этом случае удаление верщины V (и, конечно, всех инцидентных ей ребер) отделит вершину w и всех ее потомков от остальной части графа. Если же low[w] < dfnumber{v]j:o сушествует путь по ребрам дерева к потомкам вершины w и обратное ребро от какого-нибудь из этих потомков к истинному предку вершины v (именно значению dfnumber для этого предка равно low[w\). Поэтому в данном случае удаление вершины v не отделит от графа поддерево с корнем w.

Пример 7.8. Числа dfnumber и low, подсчитанные для вершин графа из рис. 7.8,а, показаны на рис. 7.11. В этом примере вычисление чисел low начато в обратном порядке с верщины е. Из этой вершины выходят обратные ребра (е, а) и (е, Ь), поэтому tou>[e] = Tmn(dfTiurnber\e\,dfTiurrtber\a],dfnurnbeT\b]y= 1. Затем рассматривается верщина d, для нее low{d\ находится как минимум чисел dfnumber[d\,k>u{e\ и dfnumber[d\. Здесь число ioii»[e]участвует потому, что вершина е является сыном вершины d, а число dfnumber\a\- из-за того, что сушествует обратное ребро (d, а).

Для определения точек сочленения после вычисления всех чисел low просматривается каждая вершина остовного дерева. Корень а является точкой сочленения, так как имеет двух сыновей. Вершина с также является точкой сочленения - для ее сына, верщины /, выполняется неравенство low[f\> rf/nam&er[c].Другие вершины не являются точками сочленения. □

Время выполнения описанного алгоритма на графе с п верщинами и е ребрами имеет порядок 0(e). Читатель легко проверит, что время, затрачиваемое на выполнение каждого этапа алгоритма, зависит или от количества посещаемых вершин, или от количества ребер, инцидентных этим верщинам, т.е. в любом случае время выполнения, с точностью до константы пропорциональности, является функцией как количества вершин, так и количества ребер. Поэтому обшее время выполнения алгоритма имеет порядок 0(п + е) или 0(e), что то же самое при п < е.





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.0017