Обход в глубину (DFS)

Как употребить эту книгу.

Как лучше всего употребить эту книгу? Надо отдать ей много времени. И ещё одно. Я рекомендую вам в будущем возвращаться к ней снова и снова. Чем больше вы взрослеете во Христе, тем больше раскрывается её значение. Эта книга увлечёт вас в 20 лет, пробудит вас в 30 лет; сокрушит вас в 40 лет и в последующие годы будет всё так же призывать в глубины Христа. Возвращайтесь к ней снова и снова.

Впервые эта книга попала мне в руки в очень плохом перепечатанном издании. Тот, кто подготовил это издание, добавил предисловие. Я до сих пор помню суть первых слов. Я окончу эпилог этими словами: "Эта маленькая книга попала вам в руки в знак того, что Бог желает произвести особую работу в вашем сердце".

Помечать каждую вершину при входе в нее, и никогда не ходить в уже помеченные вершины:

void DFS(int v){ if (mark[v]!= 0) { return; } // Если мы здесь уже были, то тут больше делать нечего mark[v] = 1; // Помечаем, что мы здесь были if (v == finish) // Проверяем, конец ли { cout << "Hooray! The path was found!\n"; return; } for (int i = 0; i < (int)edges[v].size(); ++i) // Для каждого ребра { DFS(edges[v][i]); // Запускаемся из соседа }}

И что с того?

Да, программа прошла по какому-то пути, но как определить, по какому?
Будем для каждой вершины запоминать, откуда мы в нее пришли, в специальном массиве prior. (DFS_2)

void DFS(int v, int from){ if (mark[v]!= 0) // Если мы здесь уже были, то тут больше делать нечего { return; } mark[v] = 1; // Помечаем, что мы здесь были prior[v] = from; // Запоминаем, откуда пришли if (v == finish) // Проверяем, конец ли { cout << "Hooray! The path was found!\n"; return; } for (int i = 0; i < (int)edges[v].size(); ++i) // Для каждого ребра { DFS(edges[v][i], v); // Запускаемся из соседа }}

Тогда задача восстановления пути будет тривиальной: get_path

vector<int> get_path(){ vector<int> ans; for (int v = finish; v!= start; v = prior[v]) // Проходим по пути из конца в начало { ans.push_back(v); // Запоминаем вершину } ans.push_back(start); reverse(ans.begin(), ans.end()); // Переворачиваем путь return ans;}

А почему это работает?

Алгоритм всегда найдет путь до вершины, если он существует.

Доказательство: Для произвольного графа G:
База. Пути из не более, чем 1 вершины алгоритм находит верно (путь от начальной вершины до нее же).
Предположение: Алгоритм посещает все вершины, находящиеся на расстоянии не более, чем k — 1, от начальной.
Шаг: Рассмотрим любую вершину v, находящуюся на расстоянии k от начальной. Она, очевидно, соединена ребром с какой-то вершиной, находящейся на расстоянии k — 1 от начальной — назовем ее w. Значит, мы перейдем в вершину v при просмотре вершины w.

Сколько ресурсов требуется алгоритму?

Алгоритм просматривает каждое ребро 1 раз, и выполняет для каждой вершины const число действий, число вершин - V, а ребер — E, тогда время работы — O(V+E).
Глубина рекурсии, в которой мы находимся, не превышает общего числа вызовов функции DFS — числа вершин. То есть, объем памяти, необходимый для работы алгоритма, равен O(V).

Дата добавления: 2015-06-27