Как представлять граф и выполнять обход в глубину или ширину?

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

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

В таблице n × n ячейка показывает наличие или вес ребра. Память составляет O(n²) независимо от числа рёбер. Для неориентированного графа матрица симметрична, если нет дополнительной асимметричной информации.

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

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

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

DFS идёт по одному пути до невозможности продолжить, затем возвращается. Его реализуют рекурсией или явным стеком. Массив visited предотвращает повторные посещения и зацикливание; пометка должна происходить при обнаружении вершины, а не после полного обхода.

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

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

Выбор и проверка

Оба обхода работают за O(n + m) на списках смежности. DFS удобен для компонент и структуры, BFS — для кратчайших невзвешенных путей. Протрассируйте граф с циклом, изолированной вершиной и несколькими компонентами; порядок обхода зависит от порядка соседей, но множество достижимых вершин — нет.

Представление выбирают по плотности графа

Список смежности занимает O(V + E) памяти и позволяет пройти исходящие рёбра вершины пропорционально их числу. Матрица занимает O(V²), зато проверяет наличие ребра за O(1). Для разреженной сети с миллионами вершин матрица часто непрактична; для небольшого плотного графа она может упростить вычисления.

from collections import deque

def bfs_distances(graph: list[list[int]], start: int) -> list[int]:
    distance = [-1] * len(graph)
    distance[start] = 0
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            if distance[neighbour] == -1:
                distance[neighbour] = distance[vertex] + 1
                queue.append(neighbour)
    return distance

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

Практика: маршруты между аудиториями

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