Обход DAG на C#: полное руководство

Ациклический ориентированный граф (DAG) - это структура данных, в которой рёбра имеют направление и отсутствуют циклы. Обход такого графа от начала до конца требуется во многих задачах: от планирования зависимостей до анализа данных. В этой статье мы разберём, как записать DAG для прохода на C#, используя топологическую сортировку, поиск в глубину (DFS) и поиск в ширину (BFS).

Что такое DAG и зачем его обходить?

DAG (Directed Acyclic Graph) - ориентированный граф без циклов. Обход DAG «от начала до конца» означает посещение всех узлов в порядке, который учитывает направление рёбер, начиная с истоков (узлов без входящих рёбер) и заканчивая стоками (узлами без исходящих рёбер). Это полезно для:

• Построения порядка выполнения задач (например, в системах сборки)
• Обработки зависимостей в компиляторах
• Анализа данных в графовых базах

Топологическая сортировка - основной алгоритм

Топологическая сортировка - это линейный порядок узлов DAG, при котором для каждого ребра (u → v) узел u идёт раньше v. Реализация на C# может использовать алгоритм Кана (Kahn) или DFS с отслеживанием времени выхода.

Алгоритм Кана (BFS-подход)

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

public List<int> TopologicalSortKahn(Dictionary<int, List<int>> graph, int verticesCount){    var inDegree = new int[verticesCount];    foreach (var node in graph)        foreach (var neighbor in node.Value)            inDegree[neighbor]++;    var queue = new Queue<int>();    for (int i = 0; i < verticesCount; i++)        if (inDegree[i] == 0) queue.Enqueue(i);    var result = new List<int>();    while (queue.Count > 0)    {        int u = queue.Dequeue();        result.Add(u);        if (graph.ContainsKey(u))            foreach (var v in graph[u])                if (--inDegree[v] == 0)                    queue.Enqueue(v);    }    return result.Count == verticesCount ? result : null; // null если граф не DAG}

Топологическая сортировка через DFS

Альтернативный метод - использовать рекурсивный обход с временными метками.

public List<int> TopologicalSortDFS(Dictionary<int, List<int>> graph, int verticesCount){    var visited = new bool[verticesCount];    var result = new Stack<int>();    void Dfs(int u)    {        visited[u] = true;        if (graph.ContainsKey(u))            foreach (var v in graph[u])                if (!visited[v]) Dfs(v);        result.Push(u);    }    for (int i = 0; i < verticesCount; i++)        if (!visited[i]) Dfs(i);    return result.ToList();}

Практический пример: обход DAG от начала до конца

Допустим, есть граф: 0 → 1, 0 → 2, 1 → 3, 2 → 3. Исток - узел 0, сток - узел 3. Топологическая сортировка даст: [0, 1, 2, 3] или [0, 2, 1, 3]. Оба варианта корректны. Для обхода «от начала до конца» достаточно выполнить топологическую сортировку и вывести узлы в полученном порядке.

Особенности реализации на C#

• Используйте словарь для представления графа, где ключ - узел, значение - список соседей.
• Проверяйте на циклы: топологическая сортировка возвращает null, если граф не DAG.
• Оптимизируйте память: для больших графов используйте массивы вместо списков.

Альтернативные методы обхода DAG

Если не требуется строгий порядок, можно применить обычные BFS или DFS, начиная с истоков. BFS гарантирует обход по уровням, DFS - глубокое погружение.

Поиск в ширину (BFS) для DAG

public void BfsFromSources(Dictionary<int, List<int>> graph, int verticesCount){    var inDegree = new int[verticesCount];    foreach (var node in graph)        foreach (var v in node.Value) inDegree[v]++;    var queue = new Queue<int>();    for (int i = 0; i < verticesCount; i++)        if (inDegree[i] == 0) queue.Enqueue(i);    while (queue.Count > 0)    {        int u = queue.Dequeue();        Console.WriteLine(u);        if (graph.ContainsKey(u))            foreach (var v in graph[u])                if (--inDegree[v] == 0) queue.Enqueue(v);    }}

Заключение

Обход DAG на C# проще всего реализовать через топологическую сортировку. Алгоритм Кана (на основе очереди) и DFS-подход работают за O(V+E). Выбор зависит от контекста: Кана даёт явный порядок, DFS - компактный рекурсивный код. Всегда проверяйте граф на ацикличность перед обходом.