07.08.259. Обход в глубину - justjune/AiSD2026 GitHub Wiki

Отличие от обхода в ширину

Существуют два основных алгоритма обхода графа: обход в ширину (BFS - breadth-first search) и обход в глубину (DFS - depth-first search). Для некоторых задач нет разницы, какой алгоритм использовать, для других разница может быть критической.

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

♦ Очередь - случай обхода в ширину:

В очереди типа FIFO (first-in, first-out) первыми исследуются самые старые неисследованные вершины, то есть исследование медленно распространяется вширь от стартовой вершины.

♦ Стек - случай обхода в глубину:

В стеке с порядком извлечения LIFO (last-in, first-out) при помещении в него новой вершины она сразу обрабатывается, затем посещается соседняя ей вершина, соседняя соседней и так до тех пор, пока все вершины вокруг последней посещенной не будут исследованы. Получается своего рода "змейка". Затем алгоритм возвращается к последней посещенной вершине, у которой еще остались непосещенные соседи и повторяет обход.

Псевдокод

У Скиены реализована процедура обхода, отслеживающая время обхода для каждой вершины: каждый вход в вершину и выход из неё считаются затратными по времени и инкрементируют счетчик time (добавляют к нему единицу), т.е. для каждой вершины ведется учет затрат времен на вход и выход.

Явного использования стека в реализации процедуры обхода в глубину можно избежать рекурсией. Псевдокод алгоритма представлен на листинге 7.16:

DFS(G, u)
    state[u]="discovered"
    обработать вершину u, если необходимо
    time+=1
    entry[u]=time
    для каждой вершины v, смежной с вершиной u
        обработать ребро (u, v), если необходимо
        если state[v]="undiscovered", то
            p[v]=u
            DFS(G, v)
    state[u]="processed"
    exit[u]=time
    time+=1

Особенности

При обходе в глубину интервалы времени, потраченного на посещение вершин, обладают несколькими интересными свойствами:

♦ Посещение предшественника

Для вершины x, являющейся предшествующей по отношению к вершине y в дереве обхода в глубину, подразумевается, что она должна быть посещена раньше вершины y. Кроме того, выйти из вершины x можно только после выхода из вершины y, поскольку сам алгоритм предотвращает выход из вершины x до тех пор, пока не были найдены все её потомки.

♦ Количество потомков

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

Время входа и выхода будет использоваться в дальнейших приложениях обхода в глубину. Также нужно будет выполнять разные действия при каждом входе и выходе из вершины, для чего из процедуры dfs буду вызываться функции process_vertex_early() и process_vertex_late() (по аналогии с процедурой bfs - см. 07.06.254. Применение обхода )

Другим свойством обхода в глубину является разбитие ребер неориентированного графа на древесные (tree edges) и обратные (back edges). Древесные используются при открытии новых вершин и используются в отношениях "родитель-потомок" в дереве обхода (т.е. являются частями этого дерева). Обратные ребра - это ребра, у которых второй конец является предшественником рассматриваемой вершины, и потому они направлены обратно к древу (т.е. не являются частями дерева обхода)

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

Реализация

Обход в глубину можно рассматривать как обход в ширину с использованием стека вместо очереди для хранения необработанных вершин. Но, опять-таки, рекурсия позволяет обойтись без явного использования стека, что показано на листинге 7.17:

void dfs(grap *g, int v){       //v - текущая вершина
    edgenode *p;                //Временный указатель
    int y;                      //соседняя вершина

    if(finished){               //шаманство
        return;
    }
    discovered[v]=true;         //вершина помечена как открытая
    time=time+1;
    entry_time[v]=time;         //фиксация времени входа

    process_vertex_early(v);

    p=g->edges[v];                   //переход к ребрам текущей вершины
    while(p!=NULL){                  //если ребра остались
        y=p->y;                      //просмотр соседа
        if(!discovered[y]){          //если сосед не исследован
            parent[y]=v;             //то текущая вершина - ее родитель
            process_edge(v,y);
            dfs(g,y);                //повторить процедуру для соседа
        }else if(((!processed[y]) && (parent[v]!=y)) || (g->directed)){  //особый случай
            process_edge(v,y);
        }
        if(finished){                //шаманство
            return;
        }
        p=p->next;                   //переход к следующему ребру
    }
    process_vertex_late(v);
    time=time+1;
    exit_time[v]=time;        //фиксация времени выхода
    processed[v]=true;        //вершина помечена как обработанная
}