В прошлом уроке мы разобрали три способа хранить граф — матрицу смежности, список смежности и список рёбер. Теперь у нас есть граф в памяти. Что с ним делать дальше? Первое, что нужно уметь, — это обойти его: посетить каждую вершину хотя бы один раз. Как именно обходить — зависит от задачи. Один из двух фундаментальных алгоритмов обхода — BFS, обход в ширину.

Представьте, что вы бросили камень в воду. Волна расходится от точки падения равномерно во все стороны — сначала достигает ближайшего берега, потом более далёкого. BFS работает точно так же: стартовая вершина — это камень, а «волны» — это уровни обхода.

Возьмём граф из задачи выше: шесть сотрудников, стартуем из вершины 0 (Алина).

Алина на уровне 0. Борис и Вера — на уровне 1 (один шаг от старта). Геннадий и Дмитрий — на уровне 2. Елена — на уровне 3. BFS гарантирует: когда мы впервые добираемся до вершины, мы сделали это кратчайшим путём.

Алгоритм шаг за шагом:

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

Ключевое слово — очередь. Именно FIFO (first in, first out) обеспечивает обход слоями: мы сначала обрабатываем всех соседей текущего уровня, прежде чем перейти к следующему. Если бы использовали стек — получили бы DFS (обход в глубину). Реализуем BFS на C#. Граф задан списком смежности — это выбор по умолчанию для алгоритмов обхода, потому что перебор соседей там за O(degree), а не за O(V).

Сначала — базовый обход, который просто печатает вершины по уровням:

// Список смежности графа (6 вершин: 0–5)
var graph = new Dictionary<int, List<int>>
{
    [0] = new List<int> { 1, 2 },
    [1] = new List<int> { 0, 3 },
    [2] = new List<int> { 0, 4 },
    [3] = new List<int> { 1, 5 },
    [4] = new List<int> { 2 },
    [5] = new List<int> { 3 }
};

void BfsLevels(Dictionary<int, List<int>> g, int start)
{
    var visited = new HashSet<int>();
    var queue = new Queue<int>();

    visited.Add(start);
    queue.Enqueue(start);

    int level = 0;
    while (queue.Count > 0)
    {
        // Сколько вершин в текущем уровне?
        int levelSize = queue.Count;
        var levelNodes = new List<int>();

        for (int i = 0; i < levelSize; i++)
        {
            int node = queue.Dequeue();
            levelNodes.Add(node);

            foreach (int neighbor in g[node])
            {
                if (!visited.Contains(neighbor))
                {
                    visited.Add(neighbor);    // помечаем ДО добавления в очередь
                    queue.Enqueue(neighbor);
                }
            }
        }

        Console.WriteLine($"Уровень {level}: {string.Join(", ", levelNodes)}");
        level++;
    }
}

BfsLevels(graph, 0);

Вывод:

Уровень 0: 0
Уровень 1: 1, 2
Уровень 2: 3, 4
Уровень 3: 5

Разберём ключевые детали. HashSet<int> visited хранит уже посещённые вершины — проверка за O(1). Queue<int> queue — рабочая очередь алгоритма. Важный момент: мы помечаем вершину как посещённую в момент добавления в очередь, а не в момент извлечения. Если делать наоборот — одна и та же вершина попадёт в очередь несколько раз через разных соседей, что даст дубли в выводе и лишнюю работу.

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

Для этого заводим массив parent[]: parent[v] хранит, из какой вершины мы пришли в v. Зная родителя каждой вершины, можно восстановить путь от цели до старта — а потом перевернуть.

List<int> BfsShortestPath(Dictionary<int, List<int>> g, int start, int end)
{
    var visited = new HashSet<int>();
    var queue = new Queue<int>();
    var parent = new Dictionary<int, int>();   // parent[v] = откуда пришли в v

    visited.Add(start);
    queue.Enqueue(start);
    parent[start] = -1;  // у стартовой вершины нет родителя

    while (queue.Count > 0)
    {
        int node = queue.Dequeue();

        if (node == end)
            break;  // нашли — дальше искать не нужно

        foreach (int neighbor in g[node])
        {
            if (!visited.Contains(neighbor))
            {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
                parent[neighbor] = node;  // запоминаем, откуда пришли
            }
        }
    }

    // Если цель не была достигнута
    if (!parent.ContainsKey(end))
        return new List<int>();

    // Восстанавливаем путь от конца к началу
    var path = new List<int>();
    int current = end;
    while (current != -1)
    {
        path.Add(current);
        current = parent[current];
    }

    path.Reverse();
    return path;
}

var route = BfsShortestPath(graph, 0, 5);
Console.WriteLine(string.Join(" → ", route));  // 0 → 1 → 3 → 5

Алгоритм возвращает List<int> — последовательность вершин от старта до финиша. Если пути нет (граф несвязный, цель недостижима), возвращается пустой список. Длина пути — path.Count - 1 (число рёбер), то есть количество «рукопожатий».

Теперь о том, зачем BFS существует за пределами учебных примеров.

Кратчайший путь в невзвешенном графе — первое и самое прямолинейное применение. «Через сколько промежуточных серверов пакет доходит от A до B?» — BFS. «Минимальное число ходов конём на шахматной доске из клетки A в клетку B?» — граф клеток, рёбра — допустимые ходы конём, BFS.

Обход веб-страниц (web crawling). Поисковый робот начинает с одного URL и обходит граф ссылок в ширину: сначала все ссылки с главной страницы, потом все ссылки с этих страниц. BFS гарантирует, что ближайшие по глубине страницы индексируются первыми.

«Шесть рукопожатий» в соцсетях. LinkedIn и Facebook используют BFS, чтобы показать, через кого вы связаны с нужным человеком. Уровень 1 — ваши прямые контакты, уровень 2 — контакты ваших контактов. «People you may know» — это часто вершины на уровне 2 от вас.

Обход дерева по уровням (level-order traversal). Двоичное дерево — частный случай графа. BFS по нему даёт именно обход уровень за уровнем: сначала корень, потом его дети, потом внуки. Это нужно, например, чтобы сериализовать дерево или найти ближайшего предка.

Проверка связности графа. Запустите BFS из любой вершины: если все V вершин оказались посещёнными — граф связный. Если нет — граф несвязный, и количество отдельных запусков BFS даст число компонент связности.

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

Для связного графа с V вершинами, где E ≈ V (разреженный), это линейное время — алгоритм масштабируется хорошо даже на миллионах вершин. Граф дорог России содержит ~100 000 населённых пунктов и ~300 000 дорог — BFS обойдёт его за несколько сотен миллисекунд.

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

Ключевое правило реализации: помечать вершину как посещённую при добавлении в очередь, а не при извлечении. Иначе одна вершина попадёт в очередь несколько раз.

Кратчайший путь восстанавливается через массив parent[]: для каждой вершины запоминаем, из какой вершины мы в неё пришли. Затем идём от цели к старту по цепочке родителей и переворачиваем результат.

BFS гарантирует кратчайший путь только в невзвешенном графе. Для взвешенных графов (разные стоимости рёбер) нужен алгоритм Дейкстры.

Сложность: O(V + E) по времени, O(V) по памяти.

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