4.6 Обходы графа в глубину и в ширину

Next:4.7 Усовершенствование поиска с возвращением
Up:4 Разработка алгоритмов
Previous:4.5 Обходы ордерева в глубину и ширину

4.6 Обходы графа в глубину и в ширину

Алгоритмы обхода дерева в глубину и в ширину можно модифицировать таким образом, чтобы их можно было использовать для систематического обхода всех вершин произвольного графа.

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

procedure ОБХОД-В-ГЛУБИНУ(: вершина);
begin
    Посетить вершину ;
    for allfrom множества вершин, смежных с do
        if еще не посещалась then ОБХОД-В-ГЛУБИНУ() end
    end
end;
begin
    for allfrom множества вершин do
        if еще не посещалась then ОБХОД-В-ГЛУБИНУ() end
    end
end.

В результате работы алгоритма пройденные ребра графа образуют вместе с посещенными вершинами одно или несколько деревьев (по одному дереву для каждой компоненты связности графа). Если приписать пройденным ребрам ориентацию в соответствии с тем направлением, в каком они проходятся при выполнении алгоритма, то мы получим совокупность ордеревьев, причем их корнями будут служить все те вершины, которые в процессе работы алгоритма помещались в пустой стек. Например, для графа, изображенного на рис. 21,а, описанным способом будут получены два ордерева, приведенных на рис. 21,б. Порядок на всем множестве вершин графа, а также порядок вершин, смежных всякой его вершине, соответствует алфавитному порядку букв, помечающих вершины.

Рис. 21. Граф и его обход в глубину

Нерекурсивный вариант алгоритма обхода графа в глубину может иметь следующий вид:

procedure ОБХОД-В-ГЛУБИНУ-1(: вершина);
begin
    Посетить вершину и поместить ее в пустой стек S;
    while Стек S непуст do
            Пусть -- вершина, находящаяся на верхушке стека S;
            if у есть непосещенные смежные вершины then
                    Пусть -- непосещенная вершина, смежная вершине ;
                    Пройти по ребру (), посетить вершину и поместить ее в стек S
            else Удалить вершину из стека S
            end
    end
end;

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

procedure ОБХОД-В-ШИРИНУ(: вершина);
begin
    Поместить вершину в пустую очередь O;
    while очередь O не пуста do
            Взять первую вершину из очереди O;
            if еще не посещалась then
                    Посетить вершину и поместить в очередь O все вершины, смежные с
            end
    end
end;