11.2 Представление графов¶

В алгоритмах существует несколько способов представления графов. Выбор структуры данных зависит от размера графа и того, какие операции мы планируем выполнять.

Рассмотрим три наиболее распространённых способа:

1. Представление списками смежности¶

В этом способе для каждой вершины хранится список вершин, в которые из неё есть рёбра.

Это самый популярный способ представления графа.

Идея¶

Для каждой вершины x мы храним список всех вершин, достижимых из x.

Пример графа¶

flowchart LR
    1 --> 2
    2 --> 3
    2 --> 4
    3 --> 4
    4 --> 1

Хранение¶

vector<int> adj[N];

Заполнение (пример)¶

adj[1].push_back(2);
adj[2].push_back(3);
adj[2].push_back(4);
adj[3].push_back(4);
adj[4].push_back(1);

Неориентированный граф¶

Если граф неориентированный, каждое ребро добавляется в обе стороны:

adj[a].push_back(b);
adj[b].push_back(a);

Взвешенный граф¶

Если у рёбер есть веса:

vector<pair<int,int>> adj[N];

Теперь в списке хранится (вершина, вес).

Пример¶

flowchart LR
    1 -- 5 --> 2
    2 -- 7 --> 3
    2 -- 6 --> 4
    3 -- 4 --> 4
    4 -- 2 --> 1

adj[1].push_back({2,5});
adj[2].push_back({3,7});
adj[2].push_back({4,6});
adj[3].push_back({4,4});
adj[4].push_back({1,2});

Перебор соседей¶

for (auto u : adj[s]) {
    // обработка вершины u
}

Плюсы¶

• быстро перебираются соседи вершины
• экономит память
• подходит для больших графов

2. Представление матрицей смежности¶

Здесь используется двумерный массив n × n.

Идея¶

adj[a][b] = 1, если есть ребро из a в b, иначе 0.

Пример¶

flowchart LR
    1 --> 2
    3 --> 4
    2 --> 4

Матрица¶

    1 2 3 4
1 [ 0 1 0 0 ]
2 [ 0 0 0 1 ]
3 [ 0 0 0 1 ]
4 [ 0 0 0 0 ]

Хранение¶

int adj[N][N];

Взвешенный граф¶

Вместо 0/1 храним вес:

adj[a][b] = вес ребра
adj[a][b] = INF, если ребра нет

Плюсы¶

• можно за O(1) проверить наличие ребра

Минусы¶

• требует O(n²) памяти
• не подходит для больших разреженных графов

3. Представление списком рёбер¶

В этом способе хранится просто список всех рёбер.

Хранение¶

vector<pair<int,int>> edges;

Каждая пара (a, b) означает ребро из a в b.

Пример¶

flowchart LR
    1 --> 2
    2 --> 3
    3 --> 4

edges.push_back({1,2});
edges.push_back({2,3});
edges.push_back({3,4});

Когда использовать¶

Этот способ удобен, если:

• нужно обработать все рёбра
• не требуется быстро находить соседей вершины

Сравнение¶

Вывод¶

• Списки смежности — основной выбор в большинстве задач
• Матрица — когда нужен быстрый доступ к рёбрам
• Список рёбер — когда работаем с рёбрами напрямую