При поиске в глубину посещается первая вершина, затем необходимо идти вдоль ребер графа, до попадания в тупик. Вершина графа является тупиком, если все смежные с ней вершины уже посещены. После попадания в тупик нужно возвращаться назад вдоль пройденного пути, пока не будет обнаружена вершина, у которой есть еще не посещенная вершина, а затем необходимо двигаться в этом новом направлении. Процесс оказывается завершенным при возвращении в начальную вершину, причем все смежные с ней вершины уже должны быть посещены.
Таким образом, основная идея поиска в глубину – когда возможные пути по ребрам, выходящим из вершин, разветвляются, нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными).
Алгоритм поиска в глубину
Шаг 1. Всем вершинам графа присваивается значение не посещенная. Выбирается первая вершина и помечается как посещенная.
Шаг 2. Для последней помеченной как посещенная вершины выбирается смежная вершина, являющаяся первой помеченной как не посещенная, и ей присваивается значение посещенная. Если таких вершин нет, то берется предыдущая помеченная вершина.
Шаг 3. Повторить шаг 2 до тех пор, пока все вершины не будут помечены как посещенные.
Демонстрация алгоритма поиска в глубину
//Описание функции алгоритма поиска в глубину
void Depth_First_Search(int n, int **Graph, bool *Visited,
int Node){
Visited[Node] = true;
cout << Node + 1 << endl;
for (int i = 0 ; i < n ; i++)
if (Graph[Node][i] && !Visited[i])
Depth_First_Search(n,Graph,Visited,i);
}
Также часто используется нерекурсивный алгоритм поиска в глубину. В этом случае рекурсия заменяется на стек. Как только вершина просмотрена, она помещается в стек, а использованной она становится, когда больше нет новых вершин, смежных с ней.
Временная сложность зависит от представления графа. Если применена матрица смежности, то временная сложность равна O(n2), а если нематричное представление – O(n+m): рассматриваются все вершины и все ребра.