6.5. Перебор цепей поиском в глубину

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

Хотя алгоритм изменяется минимально, сложность поиска, как пра­вило, выше, чем в варианте "а", и значительно, ибо одни и те же узлы участвуют в разных цепях, поэтому посещение узла при движении "вперед" может быть многократным. С этим связано и измене­ние в алгоритме. Делая шаг "назад" от некоторого узла Z, мы заме­няем признак R(Z)=1 признаком R(Z)=0 (узел Z вновь доступен).

Упомянутое в п. 5.4 действие j:=L приобретает принципиальное зна­чение: оно обеспечивает уникальность цепей; после возврата к узлу - Y движение "вперед" произойдет не к тому узлу, который прежде следовал за Y, а к иному (если он найдется). Поэтому две цепи поиска всегда различаются хотя бы одним узлом.

Пример 6.4.

Применим вариант "б" поиска в глубину к графу G1 (см. п.5.4) для вывода всех начинающихся в узле 5 цепей, не являющихся частью других цепей. Переменная b, принимающая значение true на шаге "вперед", нужна для распознания такой цепи. Текущая цепь пред­ставлена содержанием стека, вывод которого и производится.

Constn=9; {Значение п не должно превышать 254}

Type matr=Array[1..n,1..n] of byte; vek=Array[1..n] of byte;

Const A: matr=( (0,1,0,1,0,0,0,1,0), (1,0,1,0,0,1,0,0,0),

(0,1,0,1,1,0,1,0,0), (1,0,1,0,0,0,1,0,0),

(0,0,1,0,0,0,0,1,1), (0,1,0,0,0,0,0,0,0),

(0,'0,1,1,0,0,0,0,0), (1,0,0,0,1,0,0,0,0),

(0,0,0,0,1,0,0,0,0));

Procedure Cepi (Var A:matr; X:byte);

Var R,St:vek; b,c:Boolean; j,k,L:byte;

Begin For j:=1 to n do R[j]:=0;

k:=1;St[k]:=X; R[X]:= 1;j:=0;

RepeatL:= St[k]; {Начало главного цикла поиска в глубину}

с:= false; {Далее идет цикл поиска смежного узла j; R[j]=0}

Repeat j :=j+1;

If j > n Then c:= true

Else If (A[L,j]=1) And (R[j]=0) Then c:=true

Until с; {Или смежный узел найден,или L-я строка исчерпана}

Ifj>nThen {Шаг назад, ибо L-я строка исчерпана: }

Begin

IfbThen {Если предыдущий шаг был "вперед",выводим цепь}

Begin For j:=1 to k do Write(St[j],', '); Writeln; b:=false

End;

R[L]:=0;j:=L;k:=k-1 {Выделено специфическое действие}

End

Else {Шаг вперед, ибо подходящий смежный узел найден:}

Begin b:=true; k:=k+1; St[k]:= j; R[j]:= 1; j:= 0 End

Until k = 0

End;

BEGIN Cepi(A, 5); Readln;

END.

Даже в таком "нехитром" графе, как G1, выявляется 15 цепей, начинающихся в узле 5. При решении таких задач не пытайтесь создать "свою" систему, аккуратно встройте дополнительные действия в готовую. Например, для поиска цепи от X до Y, удовлетворяющей неким требованиям, надо включить сравнение очередного узла цепи с Y и проверку требовании. Если цепь не подходит, нужно искать следующую. Как это сделать?

• Двигаться от Y "вперед" ни к чему. Отступить от Y на шаг?

• Это годится. Достаточно передать системе управление таким образом, и автоматически будут выявлены и проверены другие цепи XY.

Итак, изменения обычно локализуются в главном цикле поиска в глубину. Если добавляемые действия - сложные, записывайте их в виде блоков, вызываемых из главного цикла.

Задание 6.5.

• Составьте блок нахождения любой цепи XY для заданных X, Y, не проходящей через заданное множество узлов.