Графы и их применение в задачах

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

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

Виды графов

• Неориентированный граф — рёбра не имеют направления, по ним можно двигаться в обе стороны.
• Ориентированный граф — рёбра имеют направление, такие рёбра называют дугами.
• Взвешенный граф — каждому ребру приписано число (вес): длина дороги, время, стоимость.

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

Граф удобно задавать матрицей смежности — квадратной таблицей, где строки и столбцы соответствуют вершинам. На пересечении ставят вес ребра, а если связи нет — ноль или прочерк. Рассмотрим граф с городами А, Б, В, Г.

Для неориентированного графа матрица симметрична относительно главной диагонали.

Поиск кратчайшего пути

Частая задача — найти путь наименьшей длины между двумя вершинами. Длина пути равна сумме весов его рёбер. Найдём кратчайший путь из А в В.

• Путь 1: А → Б → В = 5 + 2 = 7
• Путь 2: А → Г → В = 3 + 4 = 7

Оба пути дают одинаковую длину 7 — это и есть кратчайшее расстояние.

Степень вершины

Степень вершины — это число рёбер, выходящих из неё. В нашем примере вершина А связана с Б и Г, значит её степень равна двум. Сумма степеней всех вершин неориентированного графа равна удвоенному числу рёбер.

Деревья

Особый и очень важный вид графа — дерево. Это связный граф без замкнутых путей (циклов). В дереве между любыми двумя вершинами есть ровно один путь. Деревьями описывают, например, файловую систему компьютера, родословные и структуру организаций. Если в дереве n вершин, то рёбер у него ровно n - 1.

Где применяют графы

Графовые модели встречаются во многих практических задачах информатики и повседневной жизни.

Во всех этих задачах граф позволяет наглядно представить связи и применять одинаковые приёмы решения: поиск пути, проверку связности, подсчёт расстояний.

Частые ошибки. В неориентированном графе матрица смежности симметрична — нельзя заполнить только половину. Длина пути — это сумма весов рёбер, а не число вершин. При поиске кратчайшего пути нужно перебрать все возможные маршруты, а не первый попавшийся.

Как хранить граф списками соседей

Для каждой вершины храните список тех, с кем она соединена. В неориентированном графе ребро u—v нужно добавить в обе стороны. Изолированной вершине соответствует пустой список: отсутствие рёбер не означает отсутствие самой вершины.

n = 5
edges = [(0, 1), (0, 3), (1, 2), (2, 3)]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
print(adj)
# [[1, 3], [0, 2], [1, 3], [0, 2], []]

У вершины 4 нет соседей, но она учтена. В этом простом графе без петель и кратных рёбер сумма длин списков равна 8 — удвоенному числу рёбер. Не используйте adj = [[]] * n: тогда строки ссылаются на один общий вложенный список, и добавление соседа испортит сразу несколько строк.

Направления и веса

Для ориентированной дуги u → v добавляют только v в adj[u]. Во взвешенном графе элементом списка может быть пара (сосед, вес), например (3,7). В неориентированном случае обратную пару с тем же весом записывают и в список второй вершины.

Список или матрица?

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

Самопроверка: для рёбер 0—1 и 1—2 списки должны быть [[1], [0,2], [1]]. Если у вершины 1 сохранён только один сосед, вероятно, забыта обратная запись. Для графа с разрешёнными кратными рёбрами или петлями заранее определите правила представления: простая проверка по множествам может потерять кратность.

Справочные материалы: Что такое граф — исходная тема. Связанные уроки: Поиск в массиве, Алгоритмы и их эффективность.

Первоисточники: Python: структуры данных.

Кратко о главном

• Граф состоит из вершин и соединяющих их рёбер.
• Графы бывают ориентированные, неориентированные и взвешенные.
• Матрица смежности задаёт связи и веса рёбер в виде таблицы.
• Кратчайший путь — маршрут с наименьшей суммой весов рёбер.