Метод поиска в глубину

При поиске в глубину (depth-first search) анализируется первый по списку сосед текущей вершины, затем – его первый сосед и т.д. Если у некоторой вершины нет соседей, аналогичным образом анализируется второй сосед вершины, рассмотренной до нее. Таким образом, процедура поиска сразу же устремляется к вершинам, далеким от стартовой (то есть «в глубину»), и, лишь достигнув вершины, не имеющей соседей, возвращается назад.

Если упрощенно записать текст программы на псевдокоде, то он будет выглядеть следующим образом:

При вызове функции DepthFirstSearch() ей необходимо передать стартовую вершину и число 0:

Если в качестве результата функция вернула значение false, целевая вершина не найдена. В противном случае поиск закончился успешно; путь от стартовой вершины до целевой храниться в массиве Path.

Главный плюс процедуры поиска в глубину состоит в малом расходе памяти. На каждом шаге приходится хранить только вершины находящиеся на пути от стартовой вершины до текущей, да номера их просматриваемых в данный момент соседей; еще можно вспомнить о некоторых затратах на рекурсию.

Дата добавления: 2015-08-05