Поиск путей на графе в глубину

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

Рассмотрим следующую задачу. Имеется сеть железных дорог. По некоторым участкам движение возможно только в одном направлении. Известны расстояния всех участков дорог. Требуется перечислить все пути, ведущие из пункта А в пункт В, не проходящие дважды через один и тот же пункт. Приведем текст соответствующей программы.

Program Puti; { поиск путей в глубину на ориентированном графе }

Uses Crt;

Const

Max=20; { максимально допустимое число вершин графа }

Type

mat=array[1..Max,1..Max] of integer; {матрица смежности}

put=1..Max; { номер вершины в пути }

Var

Matr: mat;

M: set of put; { множество вершин, входящих в путь }

Gr: array [1..Max] of integer; { текущий путь }

A, B, Ver, K, I, J: integer;

L: boolean;

Ch: char;

Procedure ReadMat(var Matr: mat); {ввод матрицы смежности}

Begin

TextBackGround(Black);

TextColor(White);

ClrScr;

Write('Введите количество вершин графа: ');

ReadLn(Ver);

For I:=1 to Ver do

For J:=1 to Ver do

begin

Matr[I, J]:=0;

Matr[J, I]:=0

end;

Repeat

Write('Введите связи в виде пары вершин(-1-конец) ');

Read(I);

if I<>-1 then Read(J);

if (I>0) and (I<=Ver) and (J>0) and (J<=Ver) then

Matr[I,J]:=1

else if I<>-1 then WriteLn('Ошибка ввода ')

Until I = -1;

WriteLn('Ввод закончен!');

WriteLn;

ReadLn { пауза }

End;

Procedure Wiwod(Matr: Mat);

Begin

Window(46,2,75,22); { окно вывода результатов }

TextBackGround(Cyan);

ClrScr;

TextColor(LightGreen);

Write(' ');

For I:=1 to Ver do

Write(i:2); { номера столбцов матрицы }

WriteLn;

For I:=1 to Ver do

begin

TextColor(LightGreen);

Write(I:2); { номера строк матрицы }

TextColor(White);

For J:=1 to Ver do

Write(Matr[I,J]:2);

WriteLn

end

End;

Procedure PoiskPut(T: integer);

{ поиск всех путей на графе }

Var I: integer;

Begin

Gr[J]:=T; { добавление в путь текущей вершины }

M:=M+[T]; { коррекция множества вершин пути }

J:=J+1;

if T=B then { B - конечная вершина }

begin

Write('Найден путь: ');

For I:=1 to J-1 do { вывод пути }

Write(Gr[I], ' ');

WriteLn;

ReadLn { пауза }

end

else

For I:=1 to Ver do

if not (I in M) and (Matr[T,I]=1) then

{ поиск в глубину: выбор продолжения пути без цикла }

PoiskPut(I);

{ здесь оказываемся после нахождения очередного пути }

{ или в случае попадания в тупик }

M:=M-[T];

{ исключение из множества вершин пути последней вершины }

J:=J-1 { возврат в предыдущую вершину }

End;

Begin { основная программа }

ClrScr; { очистка экрана }

ReadMat(Matr); { ввод матрицы смежности }

L:=True;

While L do

begin

Wiwod(Matr);

WriteLn;

Write('Введите начальную вершину: ');

ReadLn(A);

Write('Введите конечную вершину: ');

ReadLn(B);

WriteLn;

J:=1; M:=[]; {инициализация множества вершин пути }

PoiskPut(A); { перечисление всех путей }

WriteLn('Путей больше нет! ');

Write('Повторить поиск (д/н)? ');

ReadLn(Ch);

if Ch='н' then L:=False { для выхода из цикла }

end

End.

В этой прграмме стек реализуется с помощью рекурсии. Рассмотрим порядок нахождения путей на примере. Пусть имеется граф

и требуется перечислить пути из вершины 1 в вершину 4. В процессе поиска в стеке будут находиться следующие номера вершин:

· 1;

· 1,3;

· 1,3,2;

· 1,3,2,4;

· 1,3,2;

· 1,3,2,5;

· 1,3,2,5,4;

· 1,3,2,5;

· 1,3,2;

· 1,3,4;

· 1,3;

· 1,3,6;

· 1,3;

· 1;

· 1,4;

· 1;

· Æ.

Последовательность обхода вершин графа можно представить деревом

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

Дата добавления: 2014-01-11