Как представить граф в памяти: списки и матрица смежности?

Граф хранят списками смежности — для каждой вершины список соседей, либо матрицей смежности — таблицей V×V; выбор зависит от плотности графа и частых операций.

Списки смежности

• Память O(V + E): для разреженных графов, где E ≪ V², единственный разумный выбор.
• Обход соседей вершины — за время, пропорциональное их числу: BFS и DFS идут за O(V + E).
• Проверка ребра (u, v) — O(deg(u)); при необходимости списки заменяют хеш-множествами.

Матрица смежности

• Память O(V²), зато проверка и изменение ребра — O(1).
• Оправдана для плотных графов (E ≈ V²) или небольшого числа вершин.

Другие формы

• Список рёбер (u, v, w): удобен алгоритмам Краскала и Беллмана-Форда, идущим по рёбрам.
• Неявный граф: соседи генерируются на лету — задачи про ходы коня и состояния головоломок.

Коротко для собеседования

Для разреженных графов почти всегда выбирают списки смежности: память O(V + E) и обходы за O(V + E). Матрица оправдана для плотных или маленьких графов, где нужна проверка ребра за O(1), но BFS по ней стоит уже O(V²).