Многие задачи из реального мира — это связи: города и дороги между ними, люди и их знакомства, задачи и их зависимости, страницы и ссылки. Структура, которая моделирует связи напрямую, называется граф. В отличие от деревьев (которые, кстати, частный случай графа), в графе нет корня и иерархии — только вершины и связи между ними.
Вершины и рёбра
Граф состоит из вершин (узлов) и рёбер — связей между парами вершин. Пара определений, которые задают тип графа:
- ненаправленный / направленный. В ненаправленном графе ребро двустороннее (дружба взаимна); в направленном — одностороннее, со стрелкой (задача A должна быть сделана до B).
- невзвешенный / взвешенный. У ребра может быть вес — число: длина дороги, стоимость, время. Взвешенным графам посвящена отдельная статья; здесь рёбра просто есть или нет.
Как хранить граф
Граф в программе представляют одним из двух способов.
Матрица смежности — квадратная таблица размера «вершины × вершины», где ячейка на пересечении i и j показывает, есть ли ребро между вершинами i и j. Проверить связь двух вершин — мгновенно, но таблица занимает место пропорционально квадрату числа вершин, даже если рёбер мало.
Список смежности — для каждой вершины хранят список её соседей. Экономно, когда рёбер немного (разреженный граф), а таких графов большинство. Это самый распространённый способ.
Выбор между ними — компромисс: матрица быстрее отвечает «связаны ли эти двое?», список экономит память на разреженных графах.
Два способа обойти граф
Основная операция над графом — обход: планомерно посетить все вершины, двигаясь по рёбрам. Есть два фундаментальных способа, и оба лежат в основе множества алгоритмов.
Обход в глубину (DFS, depth-first search). Идём по одному пути как можно дальше, пока не упрёмся в тупик (вершину без непосещённых соседей), затем возвращаемся на шаг назад и пробуем другой путь. Это поведение естественно выражается стеком или рекурсией. DFS — как прохождение лабиринта с правилом «держись одной стены»: заходим вглубь, при тупике откатываемся.
Обход в ширину (BFS, breadth-first search). Наоборот, исследуем граф «слоями»: сначала всех непосредственных соседей стартовой вершины, потом соседей соседей, и так волной. Это поведение выражается очередью. Важное свойство BFS: он находит вершины в порядке удалённости от старта, поэтому им находят кратчайший путь по числу рёбер в невзвешенном графе.
Разница проста: DFS ныряет вглубь и откатывается (стек), BFS расходится волнами (очередь).
Что дают обходы
На обходах строится масса полезного:
- связность. Обход из вершины посещает всё, до чего можно дойти, — так проверяют, связен ли граф и на какие компоненты он распадается.
- остовное дерево (spanning tree). Рёбра, по которым прошёл обход, образуют дерево, связывающее все вершины без циклов, — «скелет» графа.
- топологическая сортировка. В направленном графе без циклов (например, «задача A перед задачей B») можно выстроить вершины в линейный порядок, где каждая зависимость идёт раньше зависящего. Так планировщики определяют порядок сборки, выполнения задач, изучения курсов — всё, где одно должно предшествовать другому.
Коротко
- Граф — вершины и рёбра между ними; моделирует связи (сети, маршруты, зависимости). Бывает направленным/ненаправленным и взвешенным/невзвешенным.
- Хранят двумя способами: матрица смежности (быстрый ответ о связи, но память ~вершин²) и список смежности (экономно для разреженных графов).
- Обход в глубину (DFS) ныряет вглубь и откатывается — стек/рекурсия; обход в ширину (BFS) расходится волнами — очередь и находит кратчайший путь по числу рёбер.
- На обходах строят проверку связности, остовное дерево и топологическую сортировку зависимостей.
Дальше — взвешенные графы: когда у рёбер есть вес, появляются задачи о минимальном остове и кратчайшем пути (алгоритм Дейкстры).