Поиск в глубину
Идея метода. Поиск начинается с некоторой фиксированной вершины 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. Для рекурсивного поиска минимального пути вводится дополнительное условие, накапливаемый путь должен быть минимальным.