Граф как структура данных: матрица смежности, список смежности и список рёбер на Python
Что такое граф в программировании: вершины и рёбра, ориентированный, неориентированный и взвешенный граф. Три представления графа в памяти с кодом на Python и сравнением по памяти и скорости.
Коротко
Граф — это набор объектов (вершин) и связей между ними (рёбер). Ниже — число вершин, — число рёбер.
| Представление | Память | Есть ли ребро u–v | Все соседи u | Когда брать |
|---|---|---|---|---|
| Матрица смежности | вершин мало (до пары тысяч) или граф плотный | |||
| Список смежности | почти всегда: обходы, кратчайшие пути | |||
| Список рёбер | рёбра нужно сортировать или перебирать по одному |
- Ориентированный граф: ребро
u → vработает в одну сторону. Неориентированный: в обе. - Взвешенный граф: у ребра есть число — длина, цена, время.
- В 9 случаях из 10 правильный ответ — список смежности. Матрица нужна, когда важна мгновенная проверка ребра, а вершин немного.
- Граф не обязан лежать в памяти целиком: клеточное поле — тоже граф, соседей в нём считают на лету.
Эта статья про то, как граф хранить. Алгоритмы на графах — обходы, кратчайшие пути, остовы — разобраны отдельно, ссылки на них собраны в конце.
Что такое граф простыми словами
Возьмите карту метро. Станции — это вершины, перегоны между ними — рёбра. Схема не говорит, где станции находятся на самом деле и как изогнуты тоннели. Она отвечает на один вопрос: что с чем соединено. Это и есть граф.
Формально граф — пара , где — множество вершин, а — множество рёбер, то есть пар вершин.
Та же модель подходит для множества задач:
- соцсеть: люди — вершины, дружба — рёбра;
- карта дорог: перекрёстки и дороги, у дороги есть длина;
- зависимости пакетов: пакет
Aтребует пакетB, значит есть реброA → B; - веб: страницы и ссылки между ними;
- лабиринт: свободные клетки и переходы между соседними клетками.
Граф обобщает знакомые структуры. Связный список — это граф, где из каждой вершины выходит одно ребро. Дерево — связный граф без циклов. В общем графе ограничений нет: связей может быть сколько угодно, они могут замыкаться в кольца, а часть вершин может вообще ни с чем не соединяться. Как граф соотносится с массивами, хеш-таблицами и кучами, смотрите в обзоре структур данных.
Словарь терминов
Дальше в статье один и тот же граф из пяти вершин и пяти рёбер:
0 --- 1 --- 3 --- 4
\ /
2
| Термин | Что значит | В нашем графе |
|---|---|---|
| Смежные вершины | соединены ребром | 0 и 1 смежны, 0 и 3 — нет |
| Степень вершины | сколько рёбер из неё выходит, | у 1 степень 3, у 4 — 1 |
| Путь | последовательность вершин, где соседние соединены ребром | 0 → 1 → 3 → 4 |
| Цикл | путь, который вернулся в начало | 0 → 1 → 2 → 0 |
| Связный граф | из любой вершины можно дойти до любой другой | да, связный |
| Компонента связности | «остров» вершин, достижимых друг из друга | одна |
Полезный факт: в неориентированном графе сумма степеней всех вершин равна , потому что каждое ребро считается дважды — по разу с каждого конца. Он пригодится, когда будем считать память.
Виды графов
Ориентированный и неориентированный
В неориентированном графе ребро симметрично: если Аня дружит с Борей, то и Боря дружит с Аней. В ориентированном (его ещё называют орграфом) у ребра есть направление: Аня подписана на Борю, а Боря на Аню — не обязательно.
В орграфе степень распадается на две: входящая (сколько рёбер приходит в вершину) и исходящая (сколько выходит).
Неориентированный граф можно считать частным случаем ориентированного: каждое ребро u–v — это пара u → v и v → u. В коде так и делают, это видно ниже.
Взвешенный
Если ребру приписано число, граф взвешенный. Вес — это длина дороги, цена перелёта, задержка в сети. В невзвешенном графе «кратчайший путь» означает «меньше всего рёбер», во взвешенном — «минимальная сумма весов», и алгоритмы для этих случаев разные.
Другие слова, которые встретятся
- Плотный граф: рёбер почти столько, сколько вообще возможно, . Разреженный: рёбер порядка . Реальные графы почти всегда разреженные: в соцсети миллионы людей, но у каждого сотни друзей, а не миллионы.
- DAG (directed acyclic graph) — ориентированный граф без циклов. Так устроены зависимости задач и пакетов.
- Двудольный граф: вершины делятся на две группы, рёбра идут только между группами. Подробнее в статье про двудольный граф.
- Петля — ребро из вершины в саму себя. Кратные рёбра — несколько рёбер между одной парой вершин. Граф без того и другого называют простым; в задачах стоит проверять, гарантирует ли это условие.
Представление графа в памяти
Картинку в память не положишь. Нужно решить, какие вопросы граф должен отвечать быстро. Основных два:
- Есть ли ребро между
uиv? - Какие соседи у вершины
u?
Три классических представления отвечают на них с разной скоростью и занимают разный объём памяти. Вершины будем нумеровать числами от 0 до n - 1 — так их удобно использовать как индексы.
Список рёбер
Самое прямолинейное: просто записать все рёбра подряд.
n = 5 edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)]
В таком виде граф обычно и приходит на вход: в файле, в запросе, в условии задачи. Памяти нужно — меньше некуда. Но оба главных вопроса требуют пройти весь список:
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]
Обе функции работают за . Обход графа, который спрашивает соседей у каждой вершины, выйдет в — слишком медленно.
Зато список рёбер идеален, когда рёбра обрабатываются по одному и порядок выбираете вы. Алгоритм Краскала сортирует рёбра по весу и добавляет их в минимальное остовное дерево, проверяя связность через систему непересекающихся множеств. Алгоритм Беллмана — Форда раз проходит по всем рёбрам подряд. Соседи ни там, ни там не нужны.
Матрица смежности
Заводим таблицу . В ячейке 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]
У неориентированного графа матрица симметрична относительно главной диагонали. На самой диагонали нули, пока нет петель.
Проверка ребра — одно обращение по индексу, . А чтобы получить соседей, нужно просмотреть всю строку, даже если сосед один:
print(matrix[1][3] == 1) # True print([v for v in range(n) if matrix[1][v]]) # [0, 2, 3]
Главная цена — память: ячеек независимо от числа рёбер. Для 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.
Матрица — естественный выбор для алгоритма Флойда — Уоршелла: он и так считает расстояния между всеми парами вершин, то есть заполняет таблицу .
Список смежности
Для каждой вершины храним список её соседей — и больше ничего.
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], перебор занимает , то есть ровно столько, сколько соседей. Проверка ребра 3 in adj[1] — линейный поиск по списку соседей, тоже .
Память — : списков и суммарно записей в них (вспомните факт про сумму степеней). Это легко проверить:
print([len(neighbors) for neighbors in adj]) # [2, 3, 2, 2, 1] print(sum(len(neighbors) for neighbors in adj) == 2 * len(edges)) # True
Именно в таком виде граф ждут почти все алгоритмы: обходы в глубину и ширину, алгоритм Дейкстры, топологическая сортировка. Все они устроены одинаково: взять вершину, перебрать её соседей. Со списком смежности каждое ребро просматривается один-два раза, отсюда их сложность .
Если вершины — не числа
Когда вершины — строки или другие объекты, вместо списка списков берут словарь. А если часто нужна проверка ребра, соседей хранят во множестве: поиск в set в среднем занимает .
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['Москва'])) # ['Казань', 'Сочи']
Словарь множеств даёт и быстрых соседей, и быструю проверку ребра, а памяти просит по-прежнему . Плата — константа: множество тяжелее списка, а порядок соседей в нём не гарантирован.
Одна ловушка 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]
Сравнение по памяти и скорости
| Операция | Матрица смежности | Список смежности | Список рёбер |
|---|---|---|---|
| Память | |||
Есть ли ребро u–v | |||
Перебрать соседей u | |||
| Перебрать все рёбра | |||
| Добавить ребро | |||
| Удалить ребро | |||
| Добавить вершину | (пересоздать таблицу) |
Для списка смежности на множествах проверка и удаление ребра в среднем занимают .
Асимптотика — это абстракция, поэтому измерим. Случайный неориентированный граф: 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 тысяч, то есть полпроцента.
Обратная ситуация тоже бывает. В плотном графе, где близко к , список смежности занимает те же , только с худшей константой, а проверка ребра в нём медленнее. Там матрица выигрывает.
Как выбрать
- Не знаете, что брать, — берите список смежности. Он подходит для обходов и поиска путей, а это большинство задач.
- Матрица, если вершин мало (ориентир — до пары тысяч), граф плотный, часто нужна проверка «есть ли ребро» или алгоритм сам работает с таблицей .
- Список рёбер, если алгоритм идёт по рёбрам, а не по вершинам: сортирует их, перебирает все подряд, читает из потока.
- Словарь множеств, если вершины — не числа или граф часто меняется.
Быстрая проверка по ограничениям задачи: при матрица не влезет в память никогда; при можно брать что удобнее.
Класс 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)]
Добавление, удаление и проверка ребра работают в среднем за , перебор соседей — за . Условие 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 — список смежности нашего графа из пяти вершин. Первая функция работает за , вторая — за . На собеседовании первым делом так и поступают: получили список рёбер на входе — построили 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вместо генератора списков. Все строки матрицы окажутся одним объектом. -
Матрица при большом . Посмотрите на ограничения до того, как писать код: и матрица несовместимы.
-
Ноль как «нет ребра» во взвешенной матрице. Используйте
float('inf')илиNone. -
Потеряли изолированные вершины. Если граф строится только по рёбрам, вершины без рёбер в словаре не появятся.
-
Не подумали про кратные рёбра и петли. Список смежности хранит дубликаты как есть, матрица из нулей и единиц их молча схлопывает. Для большинства алгоритмов это неважно, а при подсчёте степеней — важно.
Что спрашивают на собеседованиях
Сам вопрос «как представить граф» звучит редко, но ответ на него нужен в каждой задаче на графы: первые строки решения — это построение adj. Типичные вопросы и продолжения:
- «Почему список смежности, а не матрица?» Назовите память против и перебор соседей за против . Добавьте, когда выбрали бы матрицу.
- «Какая сложность у вашего обхода?» на списке смежности и на матрице — сложность алгоритма зависит от представления.
- «А если граф не помещается в память?» Разговор про неявные графы, потоковую обработку списка рёбер и хранение на диске.
- «Это вообще граф?» Задачи, где граф надо разглядеть: поле из клеток, зависимости курсов, цепочки преобразований слов.
Куда идти дальше, когда граф уже построен:
| Задача | Статья |
|---|---|
| Обойти граф, найти компоненты связности | BFS и DFS |
| Кратчайший путь при неотрицательных весах | алгоритм Дейкстры |
| Кратчайший путь при отрицательных весах | алгоритм Беллмана — Форда |
| Расстояния между всеми парами вершин | алгоритм Флойда — Уоршелла |
| Порядок выполнения зависимых задач | топологическая сортировка |
| Есть ли в графе цикл | поиск цикла в графе |
| Соединить все вершины минимальной ценой | минимальное остовное дерево |
| Быстро объединять компоненты связности | система непересекающихся множеств |
| Разбить вершины на две группы | двудольный граф |
Итог
Граф — это вершины и рёбра, а всё остальное — уточнения: есть ли у рёбер направление, есть ли вес. Хранить его можно тремя способами. Список рёбер — самый компактный и самый медленный на запросах. Матрица смежности отвечает «есть ли ребро» мгновенно, но съедает памяти. Список смежности занимает и сразу отдаёт соседей, поэтому используется по умолчанию.
Хороший способ закрепить: возьмите любой граф из пяти-шести вершин, запишите его всеми тремя способами руками, а потом напишите функции перевода между ними без подсказок.