← Все вопросы
Что такое граф и как его хранить (список смежности)?
15
Дошёл до графов и завис на том, как граф вообще представить в коде. Что такое список смежности и матрица смежности, и что лучше выбрать новичку?
3 ответа
24
✓ Принятый ответ — помог автору
Граф — это вершины (узлы) и рёбра (связи между ними). Карта метро, друзья в соцсети, ссылки между страницами — всё это графы.
Два способа хранить:
- Список смежности — словарь, где для каждой вершины лежит список её соседей. Экономно по памяти, удобно обходить:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C'],
}
for neighbor in graph['A']:
print(neighbor) # B, C
- Матрица смежности — таблица n×n, где matrix[i][j] = 1, если есть ребро. Быстрая проверка «есть ли ребро», но жрёт O(n²) памяти даже у разреженного графа.
Новичку и в 95% задач — бери список смежности (словарь списков). Матрицу — только когда граф маленький и плотный.
Alex Volokh автор: разложил по полочкам · 13 месяцев назад
Иван Кудрявцев словарь списков — оказывается всё так просто 👍 · 13 месяцев назад
11
Через collections.defaultdict(list) удобно строить из рёбер:
from collections import defaultdict
g = defaultdict(list)
for u, v in [('A', 'B'), ('A', 'C'), ('B', 'D')]:
g[u].append(v)
g[v].append(u) # для неориентированного
9
Список смежности = dict из списков соседей. Матрица = двумерный массив 0/1. Для разреженных графов (рёбер мало) — однозначно список, иначе матрица сожрёт память впустую.
Ваш ответ
Войдите, чтобы ответить на вопрос.
