Граф G = (V, E) — это множество вершин V и множество рёбер E, которые их соединяют. Города и дороги, люди и дружба, файлы и зависимости — всё это графы. Чтобы работать с графом в коде, сначала нужно выбрать, как его хранить.

Один граф из 5 вершин как матрица, списки смежности и список рёбер
Один граф из 5 вершин как матрица, списки смежности и список рёбер

Термины

  • ориентированный граф: ребро u -> v идёт только в одну сторону; неориентированный: в обе;
  • взвешенный граф: у каждого ребра есть число (расстояние, цена);
  • степень вершины — число её рёбер; в ориентированном графе входящую и исходящую степени считают отдельно;
  • путь — последовательность вершин, соединённых рёбрами, цикл — путь, возвращающийся в начало, граф связный, если между любыми двумя вершинами есть путь;
  • граф разреженный, если E порядка V, и плотный, если E порядка V².

Три представления

Матрица смежности — таблица n x n, где matrix[u][v] = 1, если есть ребро u -> v. Список смежности хранит для каждой вершины список её соседей. Список рёбер — просто список пар (u, v).

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