Графы, списки смежности и сетки

Для неориентированных рёбер (0,1) и (0,2) списки равны [[1,2],[0],[0]]: каждое ребро записано дважды, по одному разу у каждого конца.

Свойства рёбер называют до выбора контейнера

Граф бывает ориентированным или неориентированным: ребро u → v либо имеет направление, либо разрешает переход в обе стороны. Независимо от этого граф бывает взвешенным или невзвешенным: ребро либо хранит стоимость, либо каждый переход считается одинаковым.

Неориентированное ребро обычно записывают в списки соседей дважды, ориентированное — один раз. Для взвешенного графа сосед представлен парой (to, weight). Эти решения влияют и на память, и на корректность будущего алгоритма.

Три явных представления оптимизируют разные операции

В неориентированном списке смежности физически хранятся 2E записей, но асимптотика остаётся O(V + E). В матрице стоимость не зависит от того, сколько рёбер действительно есть.

Разреженный граф имеет намного меньше V² рёбер, поэтому матрица тратит память на отсутствующие связи. В плотном графе матрица может быть разумной: её простота и O(1) проверка ребра компенсируют O(V²) памяти.

Сетка часто является неявным графом

Клетка — вершина, а допустимый шаг к соседней клетке — ребро. Не нужно заранее строить списки для всех четырёх направлений: соседей можно генерировать по координатам во время обхода. Память тогда уходит на саму сетку и состояние visited/distance, а не на дублирование очевидных рёбер.

Как представить соседей каждой вершины?

По списку неориентированных рёбер построить соседей каждой из n вершин.

Матрица смежности для любого графа

Создать матрицу n×n и отметить каждую связь.

Почему n² ячеек расточительны для редких рёбер?

Матрица тратит O(n²) памяти даже для разреженного графа с O(n) рёбрами.

Для обхода достаточно хранить существующих соседей

Для обходов нужны только реально существующие соседи; каждое неориентированное ребро добавляется в два списка.

Что содержит adjacency после очередного ребра?

После обработки k рёбер adjacency[v] содержит ровно соседей v среди этих k рёбер.

Добавляем оба направления неориентированного ребра

Создать n пустых списков. Для ребра (u,v) проверить границы, добавить v к u и u к v. Для ориентированного добавить только направление u→v.

Список смежности на C++17 и Python 3

C++17

#include <cassert>
#include <stdexcept>
#include <utility>
#include <vector>
using namespace std;

vector<vector<int>> buildGraph(
    int vertexCount,
    const vector<pair<int, int>>& edges
) {
    if (vertexCount < 0) throw invalid_argument("negative vertex count");
    vector<vector<int>> adjacency(vertexCount);
    for (auto [from, to] : edges) {
        if (from < 0 || from >= vertexCount || to < 0 || to >= vertexCount) {
            throw out_of_range("vertex index");
        }
        adjacency[from].push_back(to);
        adjacency[to].push_back(from);
    }
    return adjacency;
}

int main() {
    auto graph = buildGraph(3, {{0, 1}, {0, 2}});
    assert((graph[0] == vector<int>{1, 2}));
    assert((graph[1] == vector<int>{0}));
    assert(graph[2] == vector<int>{0});
}

Python 3

def build_graph(
    vertex_count: int,
    edges: list[tuple[int, int]],
) -> list[list[int]]:
    if vertex_count < 0:
        raise ValueError("negative vertex count")
    adjacency = [[] for _ in range(vertex_count)]
    for start, end in edges:
        if not (0 <= start < vertex_count and 0 <= end < vertex_count):
            raise IndexError("vertex index")
        adjacency[start].append(end)
        adjacency[end].append(start)
    return adjacency


graph = build_graph(3, [(0, 1), (0, 2)])
assert graph == [[1, 2], [0], [0]]

Память O(n + m) и две записи на ребро

O(V + E) памяти и O(V + E) построения: сначала создаются V пустых списков, затем добавляются записи рёбер. Полный обход всех списков читает 2E записей в неориентированном графе.

Изолированные вершины, петли и неверные индексы

Изолированные вершины; петля; параллельные рёбра; неверный индекс; отрицательное число вершин; различие направленного и ненаправленного графа.

Тесты на направленность и степень вершины

n=0; n=3 с ребром 0–1 и изолированной 2; цепочка; петля, если она разрешена контрактом; отрицательное n отклоняется.

Как распознать граф в отношениях и переходах?

Сущности соединены произвольными отношениями; из каждого состояния нужно перечислять доступные переходы.

Когда матрица смежности действительно уместна?

Матрица смежности уместна для плотного графа или частых O(1)-проверок конкретного ребра. Список рёбер лучше, если алгоритм прежде всего сортирует или перебирает сами рёбра. Для DFS/BFS по разреженному графу список смежности обычно даёт наиболее прямую стоимость соседей.

Мини-проверка: почему сумма степеней равна 2m?

Вопрос: почему сумма длин списков неориентированного графа равна 2m? Ответ: каждое ребро записано у обоих концов.

Мини-проверка: нужно ли строить рёбра сетки?

Вопрос: нужно ли строить все рёбра сетки? Ответ: нет; четырёх соседей клетки можно вычислять по координатам.

Постройте списки для четырёх вершин

Постройте списки для рёбер (0,1),(0,2),(2,3) и выпишите степени всех четырёх вершин.

Представьте ориентированный граф самостоятельно

Задача 1

Постройте ориентированный список смежности и верните входную и исходящую степень каждой вершины.

Представление должно дешёво отдавать реальные переходы

Выбор представления определяет стоимость базовой операции «перечислить соседей».