Задача 3. Лекция. Графы. Поиск в глубину ≡

Условие

Прохождение лабиринтов

Поиск в глубину (depth-first search) отвечает на вопрос: какие части графа достижимы из заданной вершины? Это похоже на задачу обхода лабиринта: имея граф, как список смежности, мы в каждой вершине "видим" ее соседей — как в лабиринте, где мы видим соседние помещения (рис. 1) и можем в них перейти. Но если мы будем это делать без продуманного плана, то можем ходить кругами, а в какую-то часть так и не попасть.

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

procedure Explore(v: Integer);
var
    i: Integer;
begin
    used[v]  := true;

    { Эта функция зависит от конкретной задачи }
    { В ней или вместо нее может быть любой код, вызывающийся при посещении новой вершины }
    Previsit(v);

    { Граф хранится списками смежности (массив adj) }
    for i := 0 to High(adj[v]) do
        if not used[adj[v][i]] then
            Explore(adj[v][i]);

   { Эта функция также зависит от конкретной задачи }
    Postvisit(v);
end;

В нашем алгоритме указано также место для процедур Previsit и Postvisit (вызываемых до и после обработки вершины); мы увидим дальше, зачем это может быть полезно.

А пока нужно убедиться, что процедура Explore корректна. Ясно, что она обходит только достижимые из v вершины, поскольку на каждом шаге она переходит от вершины к ее соседу. Но обходит ли она все такие вершины? Допустим, что нашлась достижимая из v вершина u, до которой Explore почему-то не добралась. Рассмотрим тогда какой-нибудь путь из v в u. Пусть z — последняя вершина этого пути, которую посетила процедура Explore (сама вершина v, если других нет), а w — следующая сразу за z вершина на этом пути: (рис. 3).

Выходит, что вершину z процедура посетила, а вершину w — нет. Но так быть не может: ведь состоявшийся вызов Explore(z) должен был перебрать всех соседей z.

На рис. 4 показан вызов Explore для рассмотренного ранее графа и вершины A. Считаем, что соседи вершины перебираются в алфавитном порядке. Сплошными нарисованы ребра, которые ведут в ранее не встречавшиеся вершины. Например, когда процедура Explore находилась в вершине B, она прошла по ребру B − E, и, поскольку в E она до этого не бывала, был произведен вызов Explore для E. Сплошные ребра образуют дерево (связный граф без циклов) и поэтому называются древесными ребрами (tree edges). Пунктирные же ребра ведут в вершины, которые уже встречались. Такие ребра называются обратными (back edges).

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

procedure Dfs;
var
    v: Integer;
begin
    for v := 1 to MaxV do
        if not used[v] then
            Explore(v);
end;

Процедура Explore обходит все вершины, достижимые из данной. Для обхода всего графа алгоритм поиска в глубину (рис. 5) последовательно вызывает Explore для всех вершин (пропуская уже посещенные).

Сразу же отметим, что процедура Explore вызывается для каждой вершины ровно один раз благодаря массиву used (пометки в лабиринте). Сколько времени уходит на обработку вершины? Она включает в себя:

• O(1)-операции: пометка вершины, а также вызовы Previsit и Postvisit (мы не учитываем время внутри этих вызовов);
• перебор соседей.

Общее время зависит от вершины, но можно оценить количество операций для всех вершин вместе. Общее количество операций на шаге 1 есть O(|V|). На шаге 2 (будем говорить о неориентированном графе) каждое ребро x,y ∈ E просматривается ровно два раза: при вызовах Explore(x) и Explore(y). Общее время работы на шаге 2, таким образом, есть O(|E|). В целом время работы поиска в глубину есть O(|V| + |E|), то есть линейно. За меньшее время мы не успеем даже прочесть все вершины и ребра.

Разбор задач тренировочного турнира.