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

Граф — это пара $G = (V, E)$, где $V$ — множество вершин, $E$ — множество рёбер (пар вершин). Бывают ориентированные (рёбра имеют направление) и неориентированные, взвешенные (рёбра с весами) и нет.

Способы представления:

1. Матрица смежности — таблица $n \times n$, где $M[i][j]=1$, если есть ребро.

# 3 вершины, рёбра (0-1) и (1-2)
matrix = [
    [0, 1, 0],
    [1, 0, 1],
    [0, 1, 0],
]

1. Список смежности — словарь, ключ — вершина, значение — список соседей. Экономит память для разреженных графов.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A"],
    "D": ["B"],
}

1. Список рёбер — список пар: [("A","B"), ("B","D"), ...].

Для матрицы $n$ вершин занимает $O(n^2)$ памяти, для списка смежности — $O(n + m)$, где $m$ — число рёбер.