 |
|
Алгоритм обхода вершин графа.
Часто в прикладных задачах, сводящихся к обработке графа, необходимо, начиная с некоторой вершины графа, обойти все, связанные с ней вершины, выполняя при этом в каждой вершине некоторую обработку. Как правило, не желательно в процессе обхода попадать в уже пройденную вершину. Способы обхода (итерации) вершин и дуг графа обычно подразделяются на обходы «в глубину» (depth first) и обходы «в ширину (breadth first).
При обходах в глубину порядок прохождения вершин и ребер организуется таким образом, что сразу же после прохода по некоторому ребру поиск очередного ребра производится среди тех ребер, которые исходят из вершины, в которую мы попали при последнем проходе по ребру. Если новых непройденных ребер, исходящих из этой вершины нет, то происходит возврат к предыдущей вершине и поиск нового ребра производится из нее.
При обходах «в ширину» обход производится по принципу «расходящихся кругов». Это означает, что вслед за прохождением некоторой вершины в первую очередь рассматриваются все вершины, смежные с ней, причем все эти вершины выстраиваются в обычную очередь для рассмотрения в порядке обхода. Это приводит к тому, что при таком обходе, начав с некоторой вершины, рассмотрение новых вершин продолжается для все более и более удаленных от исходной вершины вершин. Поскольку алгоритмы обходов прежде всего связаны с понятием смежности вершин, то как в обходах «в глубину», так и в обходах «в ширину» компоненты связности графа рассматриваются по отдельности.
Схематически обход «в глубину» можно представить в виде следующего алгоритма.
while (еще есть непройденные вершины) do begin
v := (выбрать непройденную вершину);
..traverseComponent(v)
End
где рекурсивная процедура traverseComponent может быть представлена следующим алгоритмом.
procedure traverseComponent(v : integer);
Begin
(пометить v как пройденную вершину);
forw 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 notmark[w] then begin
traverseComponent(w)
End
End
end;
Begin
for v:=1 ton do mark[v] := false; { пока еще нет пройденных вершин }
for v:=1 ton 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 ton do mark[v] := false; { пока еще нет пройденных вершин }
for v:=1 ton do{ поиск непройденной вершины }
if not mark[v] then begin
s.push(v); { поместили вершину в стек }
while not s.isEmpty do begin{ обход компоненты связности }
w := s.pop; { вершина w вынимается из стека }
if notmark[w] then begin { если w не была пройдена ранее }
mark[w] := true;
{ здесь можно выполнить действия по проходу через вершину w }
p := g[w]; { p – начало списка смежности }
whilep <> nil do begin { обход списка смежности w }
u := p^.e;
{ здесь можно выполнить действия по проходу по дуге (w,u) }
if not mark[u] thens.push(u);
p := p^.next
End
End
End
End
end;
Способ обхода – «в глубину» – определяется порядком помещения и извлечения вершин из стека. Заметим, что вершины графа могут попадать в стек многократно, поэтому для того, чтобы не проходить их дважды, при извлечении из стека каждая вершина вновь проверяется на предмет того, не была ли она пройдена ранее. Если изменить порядок извлечения вершин на извлечение «в порядке очереди», то есть вынимать первой ту вершину, которая была помещена в очередь ранее других, то тот же самый алгоритм (и соответствующая процедура) будут задавать порядок обхода вершин графа «в ширину».
Комментарии к алгоритму.
1. Строго говоря, представленный алгоритм обрабатывает в общем случае не граф в целом, а компоненту связности, в которую включена первая вершина. Если граф несвязный, то, очевидно, останутся не обработанные вершины. Для модификации алгоритма достаточно после каждого исчерпания следованных верши проверять массив меток на наличие нулей. Если обнаружен некоторый элемент m[i]=0, то это означает, что он относится к другой компоненте связности и процесс можно возобновить, начав теперь с этого элемента. Обработка заканчивается, если все элементы массива m помечены значением 1.
2. С помощью предложенного алгоритма можно определять, является ли заданный граф связным, и если нет, сколько компонент связности он содержит.
Нагруженные графы
Ориентированный граф называется нагруженным,если дугам этого графа поставлены в соответствие веса, так что дуге (xi ,xj)сопоставлено некоторое число c(xi, xj)= cij, называемое длиной(или весом,или стоимостьюдуги). Длиной(или весом или стоимостью) пути s, состоящего из некоторой последовательности дуг (xi, xj), называется число l(s), равное сумме длин дуг, входящих в этот путь, т.е.
l(s)= 
причем суммирование ведется по всем дугам(xi, xj) 
s.
Матрица C = (cij) называется матрицей длин дуг или матрицей весов.
Вес (цена) дуги при графическом способе задания графа обозначается цифрой над дугой (рис. 26)
Рисунок 26.
Путь в нагруженном ориентированном графе из вершины x в вершину y, где x¹y, называется минимальным, если он имеет наименьшую длину.
Аналогично определяется минимальный маршрут в нагруженном графе.
Введем матрицу длин дуг C(G)=[cij] порядка n, причем
