Поиск в глубину

Идея метода. Поиск начинается с некоторой фиксированной вершины v. Рассматривается вершина u, смежная с v. Она выбирается. Процесс повторяется с вершиной u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, когда это вершина v, процесс просмотра закончен. Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:

Nnew: array[1..N] of boolean.

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

Логика.

procedure Pg(v:integer);{Массивы Nnew и A глобальные}

var j:integer;

begin

Nnew[v]:=false; write(v:3);

for j:=1 to N do if (A[v,j]<>0) and Nnew[j] then Pg(j);

end;

Используя метод поиска путей в графе в глубину можно написать программу, которая ищет всевозможные пути в графе от заданной вершины к другой. В представленной ниже программе используется «перебор всех возможных вариантов с возвратом».

Рассмотрим программу.

uses crt;

var a:array[1..200,1..200] of byte;

bil:array[1..200] of boolean;

put:array[1..300] of integer;

i,n,j,p,na,kon,dl,odl,kz:integer;

kol:integer;

f:text;

procedure enter;

begin

assign(f,'input.txt');

reset(f);

read(f,n);

for i:=1 to n do

begin

for j:=1 to n do

read(f,a[i,j]);

end;

close(f);

end;

procedure print;

begin

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j],' ');

writeln;

end;

end;

procedure poisk(ng,kg,c:integer);

var ii:integer;

begin

if ng=kg then begin {если дошли до конца пути, то выводим путь}

write('Путь:');

for ii:=1 to c-1 do

write(put[ii],' ');

writeln;

end

else begin { ищем промежуточные путь после ng}

for ii:=1 to n do

if (a[ng,ii]<>0) and (bil[ii]<>true){вершины связаны и текущая вершина }

then begin {не рассмотрена}

put[c]:=ii;

bil[ii]:=true;

poisk(ii,kg,c+1);{ищем путь до конечной вершины (рекурсивно)}

put[c]:=0; {c вершины ii могут быть другие пути,}

bil[ii]:=false;{поэтому открываем путь от вершины ii}

end;

end;

end;

procedure enterparam;

begin

write('введите начальную и конечную вершины');

readln(na,kon);

fillchar(bil,sizeof(bil),false);

put[1]:=na; {запомним начало пути}

bil[na]:=true; {вершина рассмотрена}

p:=1; {1 - ое звено найдено }

poisk(na,kon,p+1); {ищем следующее (2-ое звено)}

end;

begin

clrscr;

enter;

print;

enterparam;

readkey;

end.

В этой программе граф вводится из файла input.txt. В матрице смежности а

A[i,j]=

Массив bil содержит в начале значение логическое false, означает, что еще ни одна вершина не просмотрена. Массив put содержит вершины, через которые нужно пройти от na до kon, где na- начало вершину от которой ищется путь, а kon- конец вершины до которой ищется путь.

Выбор всех путей производит процедура poisk(ng,kg,c), которая вызывается рекурсивно. Путь ищется от вершины ng до вершины kg, при этом путь запоминается в массиве put. Переменная с является переменной, которая запоминает номер вершины, которая найдена в промежутке от ng до kg. Первая вершина пути совпадает с началом графа. Далее ищется следующее звено пути в графе. Если путь от начальной вершины к конечной есть ищем следующий путь, до тех пор пока не наткнемся на вершину где нет дальше путей.

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

uses crt;

var a:array[1..200,1..200] of byte;

bil:array[1..200] of boolean;

put,d:array[1..300] of integer;

i,n,j,p,na,kon,dl,odl,kz:integer;

f:text;

procedure enter;

begin

assign(f,'input.txt');

reset(f);

read(f,n);

for i:=1 to n do

begin

for j:=1 to n do

read(f,a[i,j]);

end;

close(f);

end;

procedure print;

begin

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j],' ');

writeln;

end;

end;

procedure poisk(ng,kg,c:integer);

var ii:integer;

begin

if ng=kg then begin

write('Путь:'); dl:=odl;

for ii:=1 to c-1 do

begin

d[ii]:=put[ii];

kz:=c-1;

write(put[ii],' ');

end;

writeln('dl=',dl)

end

else begin

for ii:=1 to n do

if (a[ng,ii]<>0) and (bil[ii]<>true)

and((dl=0)or(odl+a[ng,ii]<dl))

then begin

put[c]:=ii;

bil[ii]:=true;

odl:=odl+a[ng,ii];

poisk(ii,kg,c+1);

put[c]:=0;

bil[ii]:=false;

odl:=odl-a[ng,ii];

end;

end;

end;

procedure enterparam;

begin

write('введите начальную и конечную вершины');

readln(na,kon);

fillchar(bil,sizeof(bil),false);

put[1]:=na;

bil[na]:=true;

p:=1; dl:=0;

poisk(na,kon,p+1);

end;

begin

clrscr;

enter;

print;

enterparam;

write('Путь:');

for i:=1 to kz do

write(d[i],' ');

writeln('длина равна ',dl);

readkey;

end.

Идея алгоритма в точности совпадает с поиском всех путей в графе. Дополнительно вводится массив, где запоминается минимальный путь. Это массив d. Для рекурсивного поиска минимального пути вводится дополнительное условие, накапливаемый путь должен быть минимальным.

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