Графы: представление, обход (BFS/DFS), практическое применение

Введение

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

Концепция

Граф состоит из вершин (узлов) и рёбер (связей между парами вершин), может быть ориентированным (ребро имеет направление, как ссылка «A зависит от B») или неориентированным (связь симметрична, как «A и B — друзья»), и представляется в коде либо через матрицу смежности (двумерный массив, где элемент [i][j] указывает наличие ребра между вершинами i и j — простая реализация, но O(n²) памяти даже для малого числа реальных связей), либо через список смежности (для каждой вершины — список связанных с ней вершин — эффективнее по памяти для разреженных графов, где реальных связей значительно меньше, чем теоретически возможных). Обход в ширину (BFS, breadth-first search) исследует граф «слоями» — сначала все вершины на расстоянии 1 от стартовой, затем все на расстоянии 2, и так далее, что естественно для поиска кратчайшего пути в невзвешенном графе. Обход в глубину (DFS, depth-first search) идёт максимально «вглубь» по одному пути, прежде чем возвращаться и исследовать альтернативные пути, что естественно подходит для задач типа топологической сортировки или проверки наличия циклов.

Пример кода

// Представление графа через список смежности
#include <unordered_map>
#include <vector>

using Graph = std::unordered_map<QString, std::vector<QString>>;

Graph dependencyGraph = {
    {"MainModule", {"NetworkModule", "DatabaseModule"}},
    {"NetworkModule", {"CoreModule"}},
    {"DatabaseModule", {"CoreModule"}},
    {"CoreModule", {}}
};

// BFS — поиск кратчайшего пути по числу рёбер в невзвешенном графе
#include <queue>
#include <unordered_set>

QStringList bfsShortestPath(const Graph &graph, const QString &start, const QString &target)
{
    std::queue<QString> toVisit;
    std::unordered_map<QString, QString> cameFrom;
    std::unordered_set<QString> visited;

    toVisit.push(start);
    visited.insert(start);

    while (!toVisit.empty()) {
        QString current = toVisit.front();
        toVisit.pop();

        if (current == target) {
            QStringList path;
            for (QString node = target; !node.isEmpty(); node = cameFrom.value(node, "")) {
                path.prepend(node);
                if (node == start) break;
            }
            return path;
        }

        for (const QString &neighbor : graph.value(current)) {
            if (!visited.contains(neighbor)) {
                visited.insert(neighbor);
                cameFrom[neighbor] = current;
                toVisit.push(neighbor);
            }
        }
    }
    return {}; // путь не найден
}

// DFS — обнаружение циклов в графе зависимостей (важно для предотвращения циклических зависимостей модулей)
bool hasCycleDFS(const Graph &graph, const QString &node,
                  std::unordered_set<QString> &visited, std::unordered_set<QString> &inStack)
{
    visited.insert(node);
    inStack.insert(node);

    for (const QString &neighbor : graph.value(node)) {
        if (inStack.contains(neighbor)) return true; // нашли вершину, уже находящуюся в текущем пути — цикл!
        if (!visited.contains(neighbor) && hasCycleDFS(graph, neighbor, visited, inStack)) return true;
    }

    inStack.erase(node); // выходим из текущего пути обхода
    return false;
}

Пояснения к коду

Представление через unordered_map<QString, vector<QString>> показывает типичный список смежности — для каждого модуля ("MainModule") хранится список модулей, от которых он напрямую зависит, что компактно представляет разреженный граф зависимостей без затрат памяти на хранение информации об отсутствующих связях (в отличие от матрицы смежности). bfsShortestPath использует очередь (std::queue) для исследования графа слоями и карту cameFrom для восстановления конкретного пути после обнаружения целевой вершины — обход в ширину гарантирует, что путь, найденный первым достижением целевой вершины, будет кратчайшим по числу рёбер именно потому, что все вершины исследуются строго в порядке увеличения расстояния от старта. hasCycleDFS использует множество inStack, отслеживающее именно вершины текущего, активного пути обхода (а не все когда-либо посещённые вершины, как visited) — обнаружение соседа, уже находящегося в этом текущем пути, однозначно означает наличие цикла, поскольку путь от этого соседа обратно к текущей вершине уже существует, что и образует замкнутый цикл.

Подводные камни

Использование матрицы смежности для разреженного графа с большим числом вершин, где реальных связей значительно меньше теоретически возможного максимума — память O(n²) для матрицы смежности становится неприемлемо большой для графов с десятками тысяч вершин и сравнительно небольшим числом реальных связей, тогда как список смежности занимает память, пропорциональную реальному числу связей, что для разреженных графов (типичных для большинства практических задач, включая графы зависимостей модулей) значительно эффективнее.
Попытка использовать BFS для поиска кратчайшего пути во взвешенном графе (где у разных рёбер разная «стоимость» перехода, а не просто единичный шаг) — обычный BFS гарантирует кратчайший путь только по количеству рёбер, что для взвешенного графа не эквивалентно кратчайшему пути по суммарному весу (алгоритм Дейкстры, специально предназначенный именно для взвешенного случая); применение обычного BFS к взвешенному графу даёт некорректный результат, если веса рёбер существенно различаются.
Рекурсивная реализация DFS без учёта ограничения глубины стека вызовов для очень больших или глубоких графов — каждый рекурсивный вызов hasCycleDFS потребляет дополнительный кадр стека, и для графов с очень длинными путями (тысячи последовательно связанных вершин) рекурсивный DFS рискует исчерпать доступный размер стека вызовов (переполнение стека), что требует либо увеличения размера стека, либо перехода на итеративную реализацию DFS с явным, программно управляемым стеком вместо рекурсии языка.
Забытое отслеживание уже посещённых вершин при обходе графа с циклами, что приводит к бесконечному циклу обхода (повторное, бесконечное посещение одних и тех же вершин по кругу) — в отличие от деревьев, где циклы по определению невозможны, графы общего вида могут содержать циклы, и любой алгоритм обхода графа обязан явно отслеживать множество уже посещённых вершин (как visited в примерах BFS и DFS) для корректного завершения обхода за конечное время.