4. Связность графа
Граф называется связным, если каждая пара различных вершин может быть соединена, по крайней мере, одной цепью.
Подграфом неориентированного графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа. Аналогично определяется подграф ориентированного графа.
Компонентой связности неориентированного графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа.
Пусть A(G) – матрица смежности ориентированного псевдографа G=(X, A), где X={x1,…, xn}. Обозначим через Ak=[a(k)ij] k-ю степень матрицы смежности A(G).
Элемент a(k)ij матрицы Ak ориентированного псевдографа G=(X, A) равен числу всех путей (маршрутов) длины k из xi в xj.
Матрица достижимости ориентированного графа G − квадратная матрица T(G)=[tij] порядка n, элементы которой равны
Матрица сильной связности ориентированного графа D − квадратная матрица S(D)=[sij] порядка n, элементы которой равны
Матрица связности графа G − квадратная матрица S(G)=[sij] порядка n, элементы которой равны
Пример.
У неориентированного графа, изображенного на рис. 23 две компоненты связности. Первая компонента связности включает вершины x1, x2, x4, x5, а вторая состоит из одной вершины x3.
Рисунок 23.
Матрица связности этого графа имеет вид:
S =
Мы видим, что 1-ая, 2-ая, 4-ая и 5-ая строки матрицы S одинаковы.
У ориентированного графа, изображенного на рис. 24 две компоненты сильной связности. Первая компонента связности включает вершины x1, x2, x3, x5, а вторая состоит из одной вершины x4. Действительно, для любой пары вершин из множества {x1, x2, x3, x5} существует хотя бы один путь, соединяющий эти вершины. Например, путь (x1, x2, x5, x3, x1) соединяет все эти вершины. Из вершины x4 нет пути ни в одну вершину графа.
Рисунок 24.
Матрица сильной связности этого графа имеет вид:
S =
Мы видим, что 1-ая, 2-ая, 3-ая и 5-ая строки матрицы S одинаковы.
5. Алгоритм обхода вершин графа.
Часто в прикладных задачах, сводящихся к обработке графа, необходимо, начиная с некоторой вершины графа, обойти все, связанные с ней вершины, выполняя при этом в каждой вершине некоторую обработку. Как правило, не желательно в процессе обхода попадать в уже пройденную вершину. Способы обхода (итерации) вершин и дуг графа обычно подразделяются на обходы «в глубину» (depth first) и обходы «в ширину (breadth first).
При обходах в глубину порядок прохождения вершин и ребер организуется таким образом, что сразу же после прохода по некоторому ребру поиск очередного ребра производится среди тех ребер, которые исходят из вершины, в которую мы попали при последнем проходе по ребру. Если новых непройденных ребер, исходящих из этой вершины нет, то происходит возврат к предыдущей вершине и поиск нового ребра производится из нее.
При обходах «в ширину» обход производится по принципу «расходящихся кругов». Это означает, что вслед за прохождением некоторой вершины в первую очередь рассматриваются все вершины, смежные с ней, причем все эти вершины выстраиваются в обычную очередь для рассмотрения в порядке обхода. Это приводит к тому, что при таком обходе, начав с некоторой вершины, рассмотрение новых вершин продолжается для все более и более удаленных от исходной вершины вершин. Поскольку алгоритмы обходов прежде всего связаны с понятием смежности вершин, то как в обходах «в глубину», так и в обходах «в ширину» компоненты связности графа рассматриваются по отдельности.
Схематически обход «в глубину» можно представить в виде следующего алгоритма.
while (еще есть непройденные вершины) do begin
v := (выбрать непройденную вершину);
..traverseComponent(v)
end
где рекурсивная процедура traverseComponent может быть представлена следующим алгоритмом.
procedure traverseComponent(v : integer);
begin
(пометить v как пройденную вершину);
for w in (все вершины, смежные с v) do
if (w – непройденная вершина) then begin
(пометить ребро (v,w) как пройденное);
traverseComponent(w)
end
end;
Приведем более подробную реализацию этого алгоритма, когда граф представлен списками смежности. Перед описанием собственно алгоритма дадим описание типов для представления графа, отличное от использованного в предыдущих алгоритмах (с использование динамических структур данных).
type PArc = ^Arc;
Arc = record e : integer; { номер вершины, в которую входит дуга }
next : PArc; { следующая дуга в списке }
end;
{ массив списков дуг, исходящих из одной и той же вершины: }
Graph = array [1..n] of PArc;
procedure traverseGraph(var g : Graph);
var mark : array [1..n] of Boolean; { помечаем пройденные вершины }
v : integer;
procedure traverseComponent(v : integer);
var w : integer;
p : PArc;
begin
mark[v] := true; { пометили вершину v как пройденную }
{ здесь можно выполнять действия по проходу через вершину v }
p := g[v]; { выбрали список дуг, исходящих из v }
while p <> nil do begin
w := p^.e;
{ здесь можно выполнять действия по проходу по дуге (v,w) }
if not mark[w] then begin
traverseComponent(w)
end
end
end;
begin
for v:=1 to n do mark[v] := false; { пока еще нет пройденных вершин }
for v:=1 to n do begin
if not mark[v] then { вершина v еще не пройдена }
traverseComponent(v) { обход одной компоненты связности }
end
end;
Внутри описания процедуры traverseComponent комментариями помечены те места, где надо производить действия, связанные с прохождением через вершину и.или по дуге графа. Отметим, что в случае неориентированного графа фактически по каждому ребру проход осуществляется дважды – сначала в прямом, а затем в обратном направлении. Если с проходом по ребру связано некоторое действие, которое надо проделывать только один раз, то каждое пройденное ребро придется отмечать дополнительно.
Если граф несвязный, то в самом внешнем цикле процедуры traverseGraph процедура traverseComponent будет вызвана столько раз, сколько компонент связности графа имеется. Поэтому эту процедуру обхода можно применять для определения компонент связности графа.
Тот же самый алгоритм обхода можно выразить и другим способом, без использования рекурсивных процедур. Для этого потребуется организовать еще одну структуру данных для запоминания номеров тех вершин, возврат к которым будет осуществляться при невозможности найти следующую вершину для обхода. Запоминание в этой структуре данных производится по принципу стека: доступной всегда будет только последняя добавленная компонента; она же первой будет удаляться из стека. Будем считать, что имеются функции для реализации следующих операций над стеком: добавить номер вершины в стек; взять номер вершины из стека (с удалением ее из стека); проверить, есть ли еще номера вершин в стеке, или он уже пуст. Схематически процедуру можно описать следующим образом.
while (еще есть непройденные вершины) do begin
v := (произвольная непройденная вершина);
(поместить вершину v в стек);
(пройти компоненту связности, используя стек)
end;
при этом обход одной компоненты связности с помощью стека осуществляется с помощью следующего алгоритма:
while (стек не пуст) do begin
w := (взять вершину из стека);
(пройти вершину w и пометить ее как пройденную);
(поместить в стек все смежные с w еще не пройденные вершины)
end
Считая, что граф задан с помощью списков смежности вершин, уточним описание алгоритма.
procedure traverseGraph(var g : Graph);
var mark : array [1..n] of Boolean; { помечаем пройденные вершины }
s : stack; { это стек }
p : PArc; { для прохода по списку смежности }
v, u, w : integer; { промежуточные номера вершин }
begin
s.init; { инициализация стека }
for v:=1 to n do mark[v] := false; { пока еще нет пройденных вершин }
for v:=1 to n do { поиск непройденной вершины }
if not mark[v] then begin
s.push(v); { поместили вершину в стек }
while not s.isEmpty do begin { обход компоненты связности }
w := s.pop; { вершина w вынимается из стека }
if not mark[w] then begin { если w не была пройдена ранее }
mark[w] := true;
{ здесь можно выполнить действия по проходу через вершину w }
p := g[w]; { p – начало списка смежности }
while p <> nil do begin { обход списка смежности w }
u := p^.e;
{ здесь можно выполнить действия по проходу по дуге (w,u) }
if not mark[u] then s.push(u);
p := p^.next
end
end
end
end
end;
Способ обхода – «в глубину» – определяется порядком помещения и извлечения вершин из стека. Заметим, что вершины графа могут попадать в стек многократно, поэтому для того, чтобы не проходить их дважды, при извлечении из стека каждая вершина вновь проверяется на предмет того, не была ли она пройдена ранее. Если изменить порядок извлечения вершин на извлечение «в порядке очереди», то есть вынимать первой ту вершину, которая была помещена в очередь ранее других, то тот же самый алгоритм (и соответствующая процедура) будут задавать порядок обхода вершин графа «в ширину».
Комментарии к алгоритму.
1. Строго говоря, представленный алгоритм обрабатывает в общем случае не граф в целом, а компоненту связности, в которую включена первая вершина. Если граф несвязный, то, очевидно, останутся не обработанные вершины. Для модификации алгоритма достаточно после каждого исчерпания следованных верши проверять массив меток на наличие нулей. Если обнаружен некоторый элемент m[i]=0, то это означает, что он относится к другой компоненте связности и процесс можно возобновить, начав теперь с этого элемента. Обработка заканчивается, если все элементы массива m помечены значением 1.
2. С помощью предложенного алгоритма можно определять, является ли заданный граф связным, и если нет, сколько компонент связности он содержит.