Как представить граф в программе?

Граф — вершины (V) и рёбра (E) между ними. Виды: ориентированный (у ребра есть направление: подписки, зависимости) или неориентированный (дружба, дороги в обе стороны); взвешенный (у ребра есть вес: расстояние, стоимость); ациклический (DAG — нет циклов: зависимости задач).

Матрица смежности — двумерный массив V×V, где m[u][v] — есть ли ребро (или его вес).

• проверить ребро — O(1);
• перебрать соседей вершины — O(V);
• память — O(V²): для миллиона вершин нереально.

Подходит для небольших и плотных графов.

Список смежности — для каждой вершины список её соседей (словарь списков).

• память — O(V + E);
• перебрать соседей — O(степени вершины);
• проверить конкретное ребро — O(степени), или O(1) в среднем, если соседей хранить множеством.

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

Ещё бывает список рёбер — просто перечень пар (u, v, вес); удобен для алгоритмов, перебирающих все рёбра (Краскал, Беллман — Форд).

Сетка (лабиринт, карта) — тоже граф: клетки — вершины, соседние клетки — рёбра, хранить отдельно не нужно.

from collections import defaultdict

edges = [("A", "B", 4), ("A", "C", 2), ("C", "B", 1), ("B", "D", 5)]

graph = defaultdict(list)          # список смежности, ориентированный, взвешенный
for u, v, w in edges:
    graph[u].append((v, w))

graph["A"]   # [('B', 4), ('C', 2)]