Лекция 3

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

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

Процедура поиска :

void DepthFirstSearch (NODE r)

{

NODE s ; // посещаем первый узел

visit ( r ); // отмечаем его

mark ( r );

while (имеется непосещенная вершина s , смежная с r )

{

DepthFirstSearch ( s );

}

}

Особенности поиска в глубину ( Visual Prolog ):

•  возможность наличия неопределенной глубины поиска;

•  использование точки возврата.