Обходы графов

Обходом графа называется последовательное посещение всех вершин некоторой его компоненты связности (возможно с каким-то действием в каждой вершине).

В этой главе описаны два наиболее распространённых вида обходов: в глубину и в ширину. Примеры кода приведены на трёх разных языках: C++, Javascript и Haskell.

Моделирование графа

Один из самых простых (и при этом весьма эффективных) способов моделирования графов — таблица смежности: хранение для каждой вершины графа множества её соседей или же — если рёбра графа содержат какую-то дополнительную информацию (называемую весом ребра) — таблицы, сопоставляющей каждому соседу информацию на соответствующем ребре.

В этой главе нас будут интересовать только графы без весов.

Сперва приведём пример вышеописанной модели графа на языке C++. Для простоты считаем, что вершины графа — все целые числа.

#include <map>
#include <set>

using Graph = std::map<int,std::set<int>>;

// добавление ориентированного ребра
void addEdge(Graph &g, int i, int j) {
    g[i].insert(j);
}

// добавление неориентированного ребра
void addEdge2(Graph &g, int i, int j) {
    addEdge(g,i,j);
    addEdge(g,j,i);
}

// множество соседей указанной вершины
std::set<int> neighbors(Graph &g, int v) {
    return g[v];
}

Отметим, что для языка C++ характерны мутирующие операции: при изменениях объект сохраняет свою идентичность, но изменяет своё состояние. Типичный код, создающий нетривиальный граф, выглядит так:

Graph testGraph() {
    Graph g;
    addEdge2(g,1,2);
    addEdge2(g,1,3);
    addEdge2(g,2,3);
    addEdge2(g,4,5);
    addEdge2(g,5,6);
    addEdge2(g,4,7);
    addEdge2(g,7,8);
    return g;
}

В функциональных языках предпочтение отдаётся иммутабельным (т.е. неизменяемым) структурам данных: изменение моделируется созданием новой структуры, для эффективности ссылающейся на части старой.

Например, библиотека Immutable для Javascript содержит иммутабельные разновидности наиболее распространённых структур данных. В терминах структур этой библиотеки наша модель графа может выглядеть так:

const im = require("immutable") // это для nodejs
const im = Immutable            // это для браузера
// из вышенаписанных двух строчек нужно оставить одну

function emptyGraph() {
    return im.Map()
}

function addEdge(g,i,j) {
    let neighbors = g.get(i)

    if (neighbors) {
        return g.set(i,neighbors.add(j))
    }

    return g.set(i,im.Set([j]))
}

function addEdge2(g,i,j) {
    return addEdge(addEdge(g,i,j),j,i)
}

function neighbors(g,i) {
    let neighbors = g.get(i)
    
    if (neighbors) { return neighbors }
    
    return im.Set()
}

Немного большая длина кода (по сравнению с вариантом на C++) связана с отсутствием возможности задать значение по-умолчанию для тех вершин, которые ещё не хранятся в Map. Для иммутабельных структур данных характерен следующий способ построения:

function testGraph() {
    let g = emptyGraph()
    g = addEdge2(g,1,2)
    g = addEdge2(g,1,3)
    g = addEdge2(g,2,3)
    g = addEdge2(g,4,5)
    g = addEdge2(g,5,6)
    g = addEdge2(g,4,7)
    g = addEdge2(g,7,8)
    return g;
}

Ну и в завершение приведём ту же самую модель на языке Haskell.

import Data.Map(Map)
import qualified Data.Map as Map
import Data.Set(Set)
import qualified Data.Set as Set


type Graph = Map Int (Set Int)

emptyGraph :: Graph
emptyGraph = Map.fromList []

addEdge :: Int -> Int -> Graph -> Graph
addEdge i j g = Map.alter (Just . update) i g
  where 
    update Nothing  = Set.fromList [j]
    update (Just s) = Set.insert j s

addEdge2 :: Int -> Int -> Graph -> Graph
addEdge2 i j g = addEdge i j $ addEdge j i g

neighbors :: Int -> Graph -> Set Int
neighbors i g = case Map.lookup i g of
    Nothing  -> Set.empty
    (Just s) -> s

Нетривиальный граф в Haskell строится примерно так же, как и средставми Immutable в Javascript:

-- не забыть в верху программы сделать import Data.Foldable

testGraph :: Graph
testGraph = 
    foldl' go emptyGraph [(1,2), (1,3), (2,3), (4,5), (5,6), (4,7), (7,8)]
  where
    go g (i,j) = addEdge2 i j g

Наивный обход в глубину

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

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

Реализация на C++.

#include <vector>

std::set<int> component(Graph &g, int v) {
    std::vector<int> path{v};
    std::set<int> visited{};
    
    while (path.size() > 0) {
        int current_vertex = path.back();
        visited.insert(current_vertex);
        
        bool found_new = false;
        
        auto n = neighbors(g,current_vertex);
        for (int i : n) {
            if (visited.count(i) == 0) { 
                path.push_back(i);
                found_new = true; 
                break;
            }
        }
        
        if (found_new) { continue; }
        
        path.pop_back();
    }
    
    return visited;
}

Логика работы этого алгоритма весьма и весьма запутанна: двойной вложенный цикл почти никогда не способствует лёгкому восприятию. Вместо того, чтобы подробно комментировать его работу, приведём чуть менее перегруженный код на Haskell и перейдём сразу к следующему разделу.

component :: Int -> Graph -> Set Int
component i g = go [i] Set.empty
  where
    go [] s = s
    go (v:vs) s =
      let s' = Set.insert v s
          n  = neighbors v g
          d  = Set.difference n s'
      in case Set.toList d of
          [] -> go vs s'
          (next:_) -> go (next:v:vs) s'

Рекурсивный обход в глубину

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

Пусть S <g> v — объединение множества S и компоненты связности вершины v в графе g без S. Для этой операции верно следующее (попытайтесь понять, почему):

1. Если S содержит v, то S <g> v = S
2. В противном случае S <g> v = (S|{v}) <g> v_1 <g> v_2 <g> ... <g> v_n, где v_i -- соседи вершины v в графе g

Приведём сперва реализацию на Javascript:

function component(g,v) {
    let op = (s,x) => {
        if (s.has(x)) { return s }
        
        s = s.add(x)
        
        for (let n of neighbors(g,x)) { s = op(s,n) }
    }
    
    return op(im.Set(), v)
}

Ну и, как всегда, на Haskell (тут она не особо короче, но зато является дословной трансляцией определения операции <g>):

component :: Int -> Graph -> Set Int
component i g = Set.empty <> i 
  where 
    s <> v
      | v `Set.member` s = s 
      | otherwise = foldl' (<>) (Set.insert v s) (neighbors v g)

Фронтовой обход в глубину

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

Вернёмся к C++, чтобы показать, насколько более простым при таком подходе становится код:

#include <vector>

std::set<int> component(Graph &g, int v) {
    std::vector<int> border{v};
    std::set<int> visited{};
    
    while (border.size() > 0) {
        int current_vertex = border.back(); border.pop_back();
        
        if (visited.count(current_vertex)) { continue; }
        
        visited.insert(current_vertex);
        
        auto n = neighbors(g,current_vertex);
        for (int i : n) { 
            if (visited.count(i) == 0) { border.push_back(i); }
        }
    }
    
    return visited;
}

Ну и, конечно же, вариант на Haskell:

component :: Int -> Graph -> Set Int
component i g = go [i] Set.empty
  where
    go [] s = s
    go (v:vs) s
        | v `Set.member` s = go vs s
        | otherwise = 
          let s' = Set.insert v s
              n  = neighbors v g
              d  = Set.difference n s'
          in go (Set.toList d ++ vs) s'

Обход в ширину

Интересным свойством фронтового обхода в глубину является лёгкость его обобщения. Сам алгоритм в общем виде весьма прост: пока фронт не пуст

1. взять из него вершину
2. если она уже посещена, вернуться на предыдущий пункт
3. пометить взятую вершину как посещённую
4. добавить к фронту всех непосещённых соседей взятой вершины

Опционально можно убрать второй пункт или же проверку посещённости в четвёртом пункте (но гораздо лучше оставить и то, и другое).

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

Алгоритм обхода в ширину выглядит так (на C++):

#include <deque>

std::set<int> component(Graph &g, int v) {
    std::deque<int> border{v};
    std::set<int> visited{};
    
    while (border.size() > 0) {
        int current_vertex = border.front(); border.pop_front();
        
        if (visited.count(current_vertex)) { continue; }
        
        visited.insert(current_vertex);
        
        auto n = neighbors(g,current_vertex);
        for (int i : n) { 
            if (visited.count(i) == 0) { border.push_back(i); }
        }
    }
    
    return visited;
}

Единственное отличие: фронт заполняется с одного конца, а опустошается — с другого. А вот картина обхода меняется значительно: теперь алгоритм посещает вершины в порядке их удалённости от начальной (сначала те, до которых можно добраться за один шаг, потом те, до которых можно добраться за два шага и так далее).

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