Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

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] - матрица смежности графа;

вспомогательный массив visited[1..n], который мы будем для того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена);

переменная f, которая примет значение TRUE, когда путь будет найден.

Program depth_first_search;

Const n=9;

m:array[1..n, 1..n] of boolean =

(

(False, True, True, False, False, False, False, False, False),

(True, False, True, False, False, False, True, True, False),

(True, True, False, True, True, False, False, False, False),

(False, False, True, False, True, False, False, False, False),

Рекомендуем скачать другие рефераты по теме: экологические рефераты, конспект 2 класс.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата