Структура данных граф в C#

Обновлено: 31.10.2026 · 8 мин чтения

Что такое граф

Граф - это набор вершин и рёбер, которые соединяют пары вершин. На графах моделируют карты дорог, друзей в соцсети, зависимости между модулями проекта, маршруты доставки и состояния в играх. Если задачу можно описать словами "объекты и связи между ними", почти всегда подойдёт граф.

Рёбра бывают направленными и ненаправленными. В ненаправленном графе связь работает в обе стороны, как дружба в соцсети. В направленном у ребра есть начало и конец, как у ссылки между страницами. Кроме того, ребру можно назначить вес: расстояние, цену билета или время в пути. Такой граф называют взвешенным.

Способы хранения графа в памяти

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

Список смежности

Для каждой вершины хранится список соседей. Это экономный вариант для разреженных графов, где рёбер заметно меньше, чем вершин в квадрате. Память занимает O(V + E), а перебор соседей вершины идёт за время, пропорциональное их количеству. Именно этот вариант подходит для большинства задач.

Матрица смежности

Это двумерный массив размера V на V, где ячейка [i, j] показывает, есть ли ребро из i в j (или хранит его вес). Проверка наличия ребра выполняется за O(1), но память растёт как V в квадрате. Матрица выгодна для плотных графов и небольших задач вроде алгоритма Флойда. Основы работы с такими структурами описаны в статье про многомерные массивы в C#.

Список рёбер

Простой список троек "откуда, куда, вес". Такой формат удобен для алгоритмов, которые сортируют рёбра, например для построения минимального остова по Краскалу, и для чтения графа из файла.

Реализация графа на списках смежности

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

public class Graph<T> where T : notnull
{
    private readonly Dictionary<T, List<(T To, double Weight)>> _adj = new();
    private readonly bool _directed;

    public Graph(bool directed = false) => _directed = directed;

    public IEnumerable<T> Vertices => _adj.Keys;

    public void AddVertex(T vertex)
    {
        if (!_adj.ContainsKey(vertex))
            _adj[vertex] = new List<(T, double)>();
    }

    public void AddEdge(T from, T to, double weight = 1)
    {
        AddVertex(from);
        AddVertex(to);
        _adj[from].Add((to, weight));
        if (!_directed)
            _adj[to].Add((from, weight));
    }

    public IReadOnlyList<(T To, double Weight)> Neighbors(T vertex) =>
        _adj.TryGetValue(vertex, out var list)
            ? list
            : Array.Empty<(T To, double Weight)>();
}

Метод AddEdge сам создаёт отсутствующие вершины, а для ненаправленного графа добавляет ребро в обе стороны. Вес по умолчанию равен единице, так что тот же класс подходит и для невзвешенных графов. Для хранения соседей использован кортеж, а коллекции Dictionary и List знакомы по любому проекту на .NET.

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

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

public static class GraphAlgorithms
{
    public static List<T> Bfs<T>(Graph<T> graph, T start) where T : notnull
    {
        var order = new List<T>();
        var visited = new HashSet<T> { start };
        var queue = new Queue<T>();
        queue.Enqueue(start);

        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            order.Add(current);

            foreach (var (next, _) in graph.Neighbors(current))
            {
                if (visited.Add(next))
                    queue.Enqueue(next);
            }
        }
        return order;
    }
}

Метод HashSet.Add возвращает false, если элемент уже есть, поэтому отдельная проверка Contains не нужна. Каждая вершина попадает в очередь не более одного раза, и время работы составляет O(V + E).

Кратчайший путь по числу рёбер

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

public static List<T>? ShortestPath<T>(Graph<T> graph, T start, T goal) where T : notnull
{
    var parent = new Dictionary<T, T>();
    var visited = new HashSet<T> { start };
    var queue = new Queue<T>();
    queue.Enqueue(start);

    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        if (EqualityComparer<T>.Default.Equals(current, goal))
        {
            var path = new List<T> { goal };
            while (parent.TryGetValue(path[^1], out var prev))
                path.Add(prev);
            path.Reverse();
            return path;
        }

        foreach (var (next, _) in graph.Neighbors(current))
        {
            if (visited.Add(next))
            {
                parent[next] = current;
                queue.Enqueue(next);
            }
        }
    }
    return null;
}

Если цель недостижима, метод вернёт null. Для взвешенных графов с разными весами такой подход уже не годится, нужен алгоритм Дейкстры на C#.

Обход в глубину

Поиск в глубину (DFS) идёт по одной ветке до конца, затем возвращается и пробует другие. Вместо очереди используется стек, явный или неявный через рекурсию. DFS нужен для поиска циклов, компонент связности, топологической сортировки и обхода лабиринтов. О самой структуре читайте в материале про стек в C#.

public static List<T> Dfs<T>(Graph<T> graph, T start) where T : notnull
{
    var order = new List<T>();
    var visited = new HashSet<T>();
    var stack = new Stack<T>();
    stack.Push(start);

    while (stack.Count > 0)
    {
        var current = stack.Pop();
        if (!visited.Add(current))
            continue;

        order.Add(current);
        foreach (var (next, _) in graph.Neighbors(current))
        {
            if (!visited.Contains(next))
                stack.Push(next);
        }
    }
    return order;
}

Итеративная версия безопаснее рекурсивной: на очень глубоком графе рекурсия может привести к StackOverflowException, который в .NET перехватить нельзя. Порядок посещения соседей здесь обратный порядку добавления, так как стек отдаёт последний элемент первым.

Пример использования

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

var g = new Graph<string>();
g.AddEdge("Москва", "Тверь");
g.AddEdge("Москва", "Тула");
g.AddEdge("Тверь", "Великий Новгород");
g.AddEdge("Тула", "Орёл");
g.AddEdge("Орёл", "Курск");

Console.WriteLine(string.Join(" -> ", GraphAlgorithms.Bfs(g, "Москва")));
Console.WriteLine(string.Join(" -> ", GraphAlgorithms.Dfs(g, "Москва")));

var path = GraphAlgorithms.ShortestPath(g, "Москва", "Курск");
Console.WriteLine(path is null ? "Пути нет" : string.Join(" -> ", path));

Для пути от Москвы до Курска получится цепочка Москва, Тула, Орёл, Курск. BFS выведет города слоями, а DFS уйдёт сначала по одной из двух веток.

Граф на матрице смежности

Когда вершины пронумерованы числами от 0 до V-1 и рёбер много, проще хранить матрицу. Ниже минимальный вариант с весами, где отсутствие ребра обозначено бесконечностью.

public class MatrixGraph
{
    private readonly double[,] _w;
    public int Size { get; }

    public MatrixGraph(int size)
    {
        Size = size;
        _w = new double[size, size];
        for (int i = 0; i < size; i++)
            for (int j = 0; j < size; j++)
                _w[i, j] = i == j ? 0 : double.PositiveInfinity;
    }

    public void SetEdge(int from, int to, double weight, bool directed = false)
    {
        _w[from, to] = weight;
        if (!directed) _w[to, from] = weight;
    }

    public bool HasEdge(int from, int to) =>
        from != to && !double.IsPositiveInfinity(_w[from, to]);

    public double[,] FloydWarshall()
    {
        var d = (double[,])_w.Clone();
        for (int k = 0; k < Size; k++)
            for (int i = 0; i < Size; i++)
                for (int j = 0; j < Size; j++)
                    if (d[i, k] + d[k, j] < d[i, j])
                        d[i, j] = d[i, k] + d[k, j];
        return d;
    }
}

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

Поиск цикла в направленном графе

Циклические зависимости - частая проблема в сборке проектов и планировщиках задач. Цикл в направленном графе находят обходом в глубину с тремя состояниями вершины: не посещена, в обработке, завершена. Если при обходе встречается вершина "в обработке", значит, найден цикл.

public static bool HasCycle<T>(Graph<T> graph) where T : notnull
{
    var state = new Dictionary<T, int>();   // 1 - в обработке, 2 - завершена

    bool Visit(T v)
    {
        state[v] = 1;
        foreach (var (next, _) in graph.Neighbors(v))
        {
            state.TryGetValue(next, out var s);
            if (s == 1) return true;
            if (s == 0 && Visit(next)) return true;
        }
        state[v] = 2;
        return false;
    }

    foreach (var v in graph.Vertices)
    {
        state.TryGetValue(v, out var s);
        if (s == 0 && Visit(v)) return true;
    }
    return false;
}

Метод рассчитан на направленный граф, созданный через new Graph<T>(directed: true). В ненаправленном графе каждое ребро формально образует цикл из двух вершин, поэтому там нужна другая проверка, с учётом родителя.

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

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

public static List<T>? TopologicalSort<T>(Graph<T> graph) where T : notnull
{
    var inDegree = graph.Vertices.ToDictionary(v => v, _ => 0);
    foreach (var v in graph.Vertices)
        foreach (var (to, _) in graph.Neighbors(v))
            inDegree[to]++;

    var queue = new Queue<T>(inDegree.Where(p => p.Value == 0).Select(p => p.Key));
    var result = new List<T>();

    while (queue.Count > 0)
    {
        var v = queue.Dequeue();
        result.Add(v);
        foreach (var (to, _) in graph.Neighbors(v))
            if (--inDegree[to] == 0)
                queue.Enqueue(to);
    }
    return result.Count == inDegree.Count ? result : null;
}

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

Какие алгоритмы на графах стоит знать

Обход и поиск пути - только начало. В таблице собраны задачи, которые встречаются чаще всего, и подходящие под них алгоритмы.

Деревья - частный случай графа: связный граф без циклов. Структуру дерева и её особенности разбирает статья про бинарное дерево в C#.

Типичные ошибки

• Забыли пометить вершину как посещённую, и обход зацикливается на графе с циклами.
• Пометили вершину при извлечении из очереди вместо добавления в неё, из-за чего одна вершина попадает в очередь много раз.
• Применили BFS к графу с разными весами рёбер и получили путь, который не самый дешёвый.
• Выбрали матрицу смежности для графа с миллионом вершин и получили OutOfMemoryException.
• Использовали рекурсивный DFS на глубоком графе и упали по переполнению стека.
• Для ненаправленного графа добавили ребро только в одну сторону.

Готовые библиотеки

Для учебных задач и собеседований хватает собственной реализации. В реальных проектах иногда берут готовые пакеты: QuikGraph для алгоритмов на графах, Microsoft Automatic Graph Layout для визуализации, Neo4j-драйвер для графовой базы данных. Если граф небольшой и нужен только обход, лучше остаться на коллекциях .NET: отдельная зависимость обычно не окупается.

Частые вопросы