Реферат: Aлгоритмы на графах
if k=B then
Begin
f:=true;
break
End
End
End;
if f then
Begin
k:=B;
Write(B);
While Prev[k]<>0 do
Begin
Write('<-', Prev[k]);
k:=Prev[k]
end
End
else
Write('Пути из ', A, ' в ', B, ' нет')
end;
Begin
Write('A= '); readln(A);
Write('B= '); readln(B);
A_to_B(A, B)
End.
Поиск в глубину .
Идея поиска в глубину проста: отправляясь от текущей вершины, мы находим новую (еще не пройденную) смежную с ней вершину, которую помечаем как пройденную и объявляем текущей. После этого процесс возобновляется. Если новой смежной вершины нет (тупик), возвращаемся к той вершине, из которой попали в текущую, и делаем следующую попытку. Если попадем в вершину B, печатаем путь. Если все вершины исчерпаны - такого пути нет.
Заметим, что построенный таким образом алгоритм способен находить все пути из A в B, но первый найденный необязательно должен быть кратчайшим.
Как обычно, алгоритм с возвратами легче всего оформить с помощью рекурсивной процедуры. Для ее реализации нам понадобятся:
матрица m[1..n, 1..n] - матрица смежности графа;