Граф как структура данных: матрица смежности, список смежности и список рёбер на Python

Что такое граф в программировании: вершины и рёбра, ориентированный, неориентированный и взвешенный граф. Три представления графа в памяти с кодом на Python и сравнением по памяти и скорости.

15 мин чтенияструктуры данных · графы · python

Коротко

Граф — это набор объектов (вершин) и связей между ними (рёбер). Ниже VV — число вершин, EE — число рёбер.

ПредставлениеПамятьЕсть ли ребро u–vВсе соседи uКогда брать
Матрица смежностиO(V2)O(V^2)O(1)O(1)O(V)O(V)вершин мало (до пары тысяч) или граф плотный
Список смежностиO(V+E)O(V + E)O(deg⁡u)O(\deg u)O(deg⁡u)O(\deg u)почти всегда: обходы, кратчайшие пути
Список рёберO(E)O(E)O(E)O(E)O(E)O(E)рёбра нужно сортировать или перебирать по одному
  • Ориентированный граф: ребро u → v работает в одну сторону. Неориентированный: в обе.
  • Взвешенный граф: у ребра есть число — длина, цена, время.
  • В 9 случаях из 10 правильный ответ — список смежности. Матрица нужна, когда важна мгновенная проверка ребра, а вершин немного.
  • Граф не обязан лежать в памяти целиком: клеточное поле — тоже граф, соседей в нём считают на лету.

Эта статья про то, как граф хранить. Алгоритмы на графах — обходы, кратчайшие пути, остовы — разобраны отдельно, ссылки на них собраны в конце.

Что такое граф простыми словами

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

Формально граф — пара G=(V,E)G = (V, E), где VV — множество вершин, а EE — множество рёбер, то есть пар вершин.

Та же модель подходит для множества задач:

  • соцсеть: люди — вершины, дружба — рёбра;
  • карта дорог: перекрёстки и дороги, у дороги есть длина;
  • зависимости пакетов: пакет A требует пакет B, значит есть ребро A → B;
  • веб: страницы и ссылки между ними;
  • лабиринт: свободные клетки и переходы между соседними клетками.

Граф обобщает знакомые структуры. Связный список — это граф, где из каждой вершины выходит одно ребро. Дерево — связный граф без циклов. В общем графе ограничений нет: связей может быть сколько угодно, они могут замыкаться в кольца, а часть вершин может вообще ни с чем не соединяться. Как граф соотносится с массивами, хеш-таблицами и кучами, смотрите в обзоре структур данных.

Словарь терминов

Дальше в статье один и тот же граф из пяти вершин и пяти рёбер:

0 --- 1 --- 3 --- 4
 \   /
   2
ТерминЧто значитВ нашем графе
Смежные вершинысоединены ребром0 и 1 смежны, 0 и 3 — нет
Степень вершинысколько рёбер из неё выходит, deg⁡v\deg vу 1 степень 3, у 4 — 1
Путьпоследовательность вершин, где соседние соединены ребром0 → 1 → 3 → 4
Циклпуть, который вернулся в начало0 → 1 → 2 → 0
Связный графиз любой вершины можно дойти до любой другойда, связный
Компонента связности«остров» вершин, достижимых друг из другаодна

Полезный факт: в неориентированном графе сумма степеней всех вершин равна 2E2E, потому что каждое ребро считается дважды — по разу с каждого конца. Он пригодится, когда будем считать память.

Виды графов

Ориентированный и неориентированный

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

В орграфе степень распадается на две: входящая (сколько рёбер приходит в вершину) и исходящая (сколько выходит).

Неориентированный граф можно считать частным случаем ориентированного: каждое ребро u–v — это пара u → v и v → u. В коде так и делают, это видно ниже.

Взвешенный

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

Другие слова, которые встретятся

  • Плотный граф: рёбер почти столько, сколько вообще возможно, E≈V2E \approx V^2. Разреженный: рёбер порядка VV. Реальные графы почти всегда разреженные: в соцсети миллионы людей, но у каждого сотни друзей, а не миллионы.
  • DAG (directed acyclic graph) — ориентированный граф без циклов. Так устроены зависимости задач и пакетов.
  • Двудольный граф: вершины делятся на две группы, рёбра идут только между группами. Подробнее в статье про двудольный граф.
  • Петля — ребро из вершины в саму себя. Кратные рёбра — несколько рёбер между одной парой вершин. Граф без того и другого называют простым; в задачах стоит проверять, гарантирует ли это условие.

Представление графа в памяти

Картинку в память не положишь. Нужно решить, какие вопросы граф должен отвечать быстро. Основных два:

  1. Есть ли ребро между u и v?
  2. Какие соседи у вершины u?

Три классических представления отвечают на них с разной скоростью и занимают разный объём памяти. Вершины будем нумеровать числами от 0 до n - 1 — так их удобно использовать как индексы.

Список рёбер

Самое прямолинейное: просто записать все рёбра подряд.

n = 5 edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)]

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

def has_edge(edges, u, v): return (u, v) in edges or (v, u) in edges def neighbors(edges, u): result = [] for a, b in edges: if a == u: result.append(b) elif b == u: result.append(a) return result print(has_edge(edges, 2, 1)) # True print(neighbors(edges, 1)) # [0, 2, 3]

Обе функции работают за O(E)O(E). Обход графа, который спрашивает соседей у каждой вершины, выйдет в O(V⋅E)O(V \cdot E) — слишком медленно.

Зато список рёбер идеален, когда рёбра обрабатываются по одному и порядок выбираете вы. Алгоритм Краскала сортирует рёбра по весу и добавляет их в минимальное остовное дерево, проверяя связность через систему непересекающихся множеств. Алгоритм Беллмана — Форда V−1V - 1 раз проходит по всем рёбрам подряд. Соседи ни там, ни там не нужны.

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

Заводим таблицу V×VV \times V. В ячейке matrix[u][v] стоит 1, если ребро u → v есть, и 0, если нет.

matrix = [[0] * n for _ in range(n)] for u, v in edges: matrix[u][v] = 1 matrix[v][u] = 1 # граф неориентированный: ребро видно с обеих сторон for row in matrix: print(row)
[0, 1, 1, 0, 0]
[1, 0, 1, 1, 0]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 1]
[0, 0, 0, 1, 0]

У неориентированного графа матрица симметрична относительно главной диагонали. На самой диагонали нули, пока нет петель.

Проверка ребра — одно обращение по индексу, O(1)O(1). А чтобы получить соседей, нужно просмотреть всю строку, даже если сосед один:

print(matrix[1][3] == 1) # True print([v for v in range(n) if matrix[1][v]]) # [0, 2, 3]

Главная цена — память: V2V^2 ячеек независимо от числа рёбер. Для 1 000 вершин это миллион ячеек, терпимо. Для 100 000 вершин — десять миллиардов, и разговор окончен.

Обратите внимание, как создаётся матрица. Запись [[0] * n] * n выглядит короче, но создаёт n ссылок на одну и ту же строку:

bad = [[0] * 3] * 3 bad[0][1] = 1 print(bad) # [[0, 1, 0], [0, 1, 0], [0, 1, 0]]

Поставили одно ребро — получили три. Это одна из самых частых ошибок новичков на Python.

Матрица — естественный выбор для алгоритма Флойда — Уоршелла: он и так считает расстояния между всеми парами вершин, то есть заполняет таблицу V×VV \times V.

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

Для каждой вершины храним список её соседей — и больше ничего.

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

Соседи вершины u — это готовый список adj[u], перебор занимает O(deg⁡u)O(\deg u), то есть ровно столько, сколько соседей. Проверка ребра 3 in adj[1] — линейный поиск по списку соседей, тоже O(deg⁡u)O(\deg u).

Память — O(V+E)O(V + E): VV списков и суммарно 2E2E записей в них (вспомните факт про сумму степеней). Это легко проверить:

print([len(neighbors) for neighbors in adj]) # [2, 3, 2, 2, 1] print(sum(len(neighbors) for neighbors in adj) == 2 * len(edges)) # True

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

Если вершины — не числа

Когда вершины — строки или другие объекты, вместо списка списков берут словарь. А если часто нужна проверка ребра, соседей хранят во множестве: поиск в set в среднем занимает O(1)O(1).

from collections import defaultdict flights = [('Москва', 'Казань'), ('Москва', 'Сочи'), ('Казань', 'Сочи')] graph = defaultdict(set) for a, b in flights: graph[a].add(b) graph[b].add(a) print('Сочи' in graph['Казань']) # True print(sorted(graph['Москва'])) # ['Казань', 'Сочи']

Словарь множеств даёт и быстрых соседей, и быструю проверку ребра, а памяти просит по-прежнему O(V+E)O(V + E). Плата — константа: множество тяжелее списка, а порядок соседей в нём не гарантирован.

Одна ловушка defaultdict: вершина без рёбер в словарь не попадёт, пока вы к ней не обратитесь. Если изолированные вершины важны (например, считаете компоненты связности), добавьте их явно.

Ориентированный и взвешенный граф в коде

Отличий от базового варианта минимум.

Ориентированный граф — ребро добавляется только в одну сторону. Заодно удобно сразу посчитать входящие степени:

follows = [(0, 1), (0, 2), (1, 2), (3, 1), (3, 4)] out = [[] for _ in range(n)] indegree = [0] * n for u, v in follows: out[u].append(v) # только в одну сторону indegree[v] += 1 print(out) # [[1, 2], [2], [], [1, 4], []] print(indegree) # [0, 2, 2, 0, 1]

Матрица ориентированного графа перестаёт быть симметричной: matrix[u][v] и matrix[v][u] теперь независимы.

Взвешенный граф — в списке смежности вместо соседа храним пару «сосед, вес»:

roads = [(0, 1, 7), (0, 2, 3), (1, 2, 1), (1, 3, 2), (3, 4, 5)] weighted = [[] for _ in range(n)] for u, v, w in roads: weighted[u].append((v, w)) weighted[v].append((u, w)) print(weighted[1]) # [(0, 7), (2, 1), (3, 2)]

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

INF = float('inf') dist = [[INF] * n for _ in range(n)] for u in range(n): dist[u][u] = 0 for u, v, w in roads: dist[u][v] = w dist[v][u] = w print(dist[1]) # [7, 0, 1, 2, inf]

Сравнение по памяти и скорости

ОперацияМатрица смежностиСписок смежностиСписок рёбер
ПамятьO(V2)O(V^2)O(V+E)O(V + E)O(E)O(E)
Есть ли ребро u–vO(1)O(1)O(deg⁡u)O(\deg u)O(E)O(E)
Перебрать соседей uO(V)O(V)O(deg⁡u)O(\deg u)O(E)O(E)
Перебрать все рёбраO(V2)O(V^2)O(V+E)O(V + E)O(E)O(E)
Добавить реброO(1)O(1)O(1)O(1)O(1)O(1)
Удалить реброO(1)O(1)O(deg⁡u)O(\deg u)O(E)O(E)
Добавить вершинуO(V2)O(V^2) (пересоздать таблицу)O(1)O(1)O(1)O(1)

Для списка смежности на множествах проверка и удаление ребра в среднем занимают O(1)O(1).

Асимптотика — это абстракция, поэтому измерим. Случайный неориентированный граф: 2 000 вершин и 10 000 рёбер, средняя степень 10 — типичный разреженный граф.

import random import sys import timeit random.seed(1) n, m = 2000, 10000 edge_set = set() while len(edge_set) < m: u, v = random.randrange(n), random.randrange(n) if u != v and (v, u) not in edge_set: edge_set.add((u, v)) edges = list(edge_set) matrix = [[0] * n for _ in range(n)] adj = [[] for _ in range(n)] for u, v in edges: matrix[u][v] = matrix[v][u] = 1 adj[u].append(v) adj[v].append(u) def size_mb(rows): return (sys.getsizeof(rows) + sum(sys.getsizeof(row) for row in rows)) / 2**20 def walk_matrix(): return sum(1 for u in range(n) for v in range(n) if matrix[u][v]) def walk_adj(): return sum(1 for u in range(n) for v in adj[u]) print(f'матрица: {size_mb(matrix):.1f} МБ') print(f'список смежности: {size_mb(adj):.2f} МБ') print(f'обход матрицы: {timeit.timeit(walk_matrix, number=5) / 5 * 1000:.0f} мс') print(f'обход списков: {timeit.timeit(walk_adj, number=5) / 5 * 1000:.2f} мс')

На моей машине (Python 3.9) получилось так:

матрица: 30.6 МБ
список смежности: 0.33 МБ
обход матрицы: 110 мс
обход списков: 0.45 мс

Матрица занимает примерно в 90 раз больше памяти, а перебор всех рёбер по ней в 200 с лишним раз медленнее. Точные цифры зависят от машины и версии Python, порядок разницы — нет: матрица платит за 4 миллиона ячеек, из которых заняты 20 тысяч, то есть полпроцента.

Обратная ситуация тоже бывает. В плотном графе, где EE близко к V2V^2, список смежности занимает те же O(V2)O(V^2), только с худшей константой, а проверка ребра в нём медленнее. Там матрица выигрывает.

Как выбрать

  • Не знаете, что брать, — берите список смежности. Он подходит для обходов и поиска путей, а это большинство задач.
  • Матрица, если вершин мало (ориентир — до пары тысяч), граф плотный, часто нужна проверка «есть ли ребро» или алгоритм сам работает с таблицей V×VV \times V.
  • Список рёбер, если алгоритм идёт по рёбрам, а не по вершинам: сортирует их, перебирает все подряд, читает из потока.
  • Словарь множеств, если вершины — не числа или граф часто меняется.

Быстрая проверка по ограничениям задачи: при V=105V = 10^5 матрица не влезет в память никогда; при V≤500V \le 500 можно брать что удобнее.

Класс Graph на Python

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

class Graph: def __init__(self, directed=False): self.adj = {} self.directed = directed def add_vertex(self, v): self.adj.setdefault(v, {}) def add_edge(self, u, v, weight=1): self.add_vertex(u) self.add_vertex(v) self.adj[u][v] = weight if not self.directed: self.adj[v][u] = weight def remove_edge(self, u, v): self.adj[u].pop(v, None) if not self.directed: self.adj[v].pop(u, None) def has_edge(self, u, v): return v in self.adj.get(u, {}) def neighbors(self, v): return list(self.adj[v]) def edges(self): result = [] for u in self.adj: for v, weight in self.adj[u].items(): if self.directed or u <= v: result.append((u, v, weight)) return result g = Graph() for u, v, w in [(0, 1, 7), (0, 2, 3), (1, 2, 1), (1, 3, 2), (3, 4, 5)]: g.add_edge(u, v, w) print(g.neighbors(1)) # [0, 2, 3] print(g.has_edge(3, 1), g.has_edge(0, 4)) # True False g.remove_edge(1, 2) print(g.edges()) # [(0, 1, 7), (0, 2, 3), (1, 3, 2), (3, 4, 5)]

Добавление, удаление и проверка ребра работают в среднем за O(1)O(1), перебор соседей — за O(deg⁡v)O(\deg v). Условие u <= v в методе edges нужно, чтобы не вернуть каждое неориентированное ребро дважды; оно требует, чтобы вершины можно было сравнивать между собой.

Такой класс не поддерживает кратные рёбра: повторный add_edge просто перезапишет вес. Если они нужны, храните в значении список весов.

Перевод из одного представления в другое

Представления несут одну и ту же информацию, поэтому переводятся друг в друга за один проход:

def matrix_to_adj(matrix): n = len(matrix) return [[v for v in range(n) if matrix[u][v]] for u in range(n)] def adj_to_edges(adj): return [(u, v) for u in range(len(adj)) for v in adj[u] if u < v] print(adj_to_edges(adj)) # [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)]

Здесь adj — список смежности нашего графа из пяти вершин. Первая функция работает за O(V2)O(V^2), вторая — за O(V+E)O(V + E). На собеседовании первым делом так и поступают: получили список рёбер на входе — построили adj.

Граф, которого нет в памяти

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

grid = [ '..#', '.#.', '...', ] def grid_neighbors(grid, r, c): for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == '.': yield nr, nc print(list(grid_neighbors(grid, 0, 0))) # [(1, 0), (0, 1)]

Такой граф называют неявным. Вершиной может быть что угодно: клетка, расстановка фигур на доске, слово в словаре, состояние кубика Рубика. Достаточно функции «дай соседей этого состояния» — и на таком графе работают те же обходы.

На собеседованиях неявные графы встречаются чаще явных. Количество островов, поиск слова на поле, кратчайший путь в лабиринте — нигде не сказано слово «граф», но это задачи на графы. Умение увидеть в условии вершины и рёбра — половина решения.

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

  • Забыли обратное ребро. В неориентированном графе нужны обе строки: adj[u].append(v) и adj[v].append(u). Без второй обход «не видит» дорогу назад.

  • Добавили обратное ребро в орграф. Обратная ошибка: в задаче про зависимости рёбра направленные, и симметричное добавление её ломает.

  • Нумерация с единицы. В условиях вершины часто нумеруют от 1 до n. Либо вычитайте единицу при чтении, либо заводите массив размера n + 1 и не трогайте нулевую ячейку.

    def read_graph(stream): n, m = map(int, stream.readline().split()) adj = [[] for _ in range(n + 1)] # вершины в условии нумеруются с 1 for _ in range(m): u, v = map(int, stream.readline().split()) adj[u].append(v) adj[v].append(u) return adj
  • [[0] * n] * n вместо генератора списков. Все строки матрицы окажутся одним объектом.

  • Матрица при большом VV. Посмотрите на ограничения до того, как писать код: V=105V = 10^5 и матрица несовместимы.

  • Ноль как «нет ребра» во взвешенной матрице. Используйте float('inf') или None.

  • Потеряли изолированные вершины. Если граф строится только по рёбрам, вершины без рёбер в словаре не появятся.

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

Что спрашивают на собеседованиях

Сам вопрос «как представить граф» звучит редко, но ответ на него нужен в каждой задаче на графы: первые строки решения — это построение adj. Типичные вопросы и продолжения:

  • «Почему список смежности, а не матрица?» Назовите память O(V+E)O(V + E) против O(V2)O(V^2) и перебор соседей за O(deg⁡u)O(\deg u) против O(V)O(V). Добавьте, когда выбрали бы матрицу.
  • «Какая сложность у вашего обхода?» O(V+E)O(V + E) на списке смежности и O(V2)O(V^2) на матрице — сложность алгоритма зависит от представления.
  • «А если граф не помещается в память?» Разговор про неявные графы, потоковую обработку списка рёбер и хранение на диске.
  • «Это вообще граф?» Задачи, где граф надо разглядеть: поле из клеток, зависимости курсов, цепочки преобразований слов.

Куда идти дальше, когда граф уже построен:

ЗадачаСтатья
Обойти граф, найти компоненты связностиBFS и DFS
Кратчайший путь при неотрицательных весахалгоритм Дейкстры
Кратчайший путь при отрицательных весахалгоритм Беллмана — Форда
Расстояния между всеми парами вершиналгоритм Флойда — Уоршелла
Порядок выполнения зависимых задачтопологическая сортировка
Есть ли в графе циклпоиск цикла в графе
Соединить все вершины минимальной ценойминимальное остовное дерево
Быстро объединять компоненты связностисистема непересекающихся множеств
Разбить вершины на две группыдвудольный граф

Итог

Граф — это вершины и рёбра, а всё остальное — уточнения: есть ли у рёбер направление, есть ли вес. Хранить его можно тремя способами. Список рёбер — самый компактный и самый медленный на запросах. Матрица смежности отвечает «есть ли ребро» мгновенно, но съедает O(V2)O(V^2) памяти. Список смежности занимает O(V+E)O(V + E) и сразу отдаёт соседей, поэтому используется по умолчанию.

Хороший способ закрепить: возьмите любой граф из пяти-шести вершин, запишите его всеми тремя способами руками, а потом напишите функции перевода между ними без подсказок.

Потренироваться в спокойной обстановке

Все задачи