Представление и обработка графов: матрицы и списки смежности

Модуль "Графы" • урок 1 из 4 • ~12 минут

Основные понятия

Граф G = (V, E) состоит из:

• Вершин (vertices) V = {v₁, v₂, …, vₙ} - объекты, которые мы моделируем.
• Ребер (edges) E = {e₁, e₂, …, eₘ} - связи между вершинами. Каждое ребро соединяет пару вершин.

Виды графов

• Неориентированный (undirected): ребро (u, v) = (v, u). Дорога с двусторонним движением - если из А можно попасть в Б, то и из Б в А.
• Ориентированный (directed, "орграф"): ребро (u, v) ≠ (v, u). Улица с односторонним движением. Ребро указывает направление.
• Взвешенный (weighted): каждому ребру присвоен вес (число). Пример: расстояние между городами или стоимость проезда.

Терминология

• Степень вершины - количество ребер, инцидентных вершине. В орграфе различают входящую и исходящую степень.
• Путь - последовательность вершин, в которой каждая пара соседних вершин соединена ребром.
• Цикл - путь, начинающийся и заканчивающийся в одной и той же вершине.
• Связный граф - граф, в котором существует путь между любой парой вершин.
• Компонента связности - максимальный связный подграф.

Представление и обработка графов в памяти

Существует три основных способа хранить граф в программе. Каждый имеет свои плюсы и минусы.

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

Двумерный массив adj[N][N], где adj[i][j] = 1, если существует ребро из вершины i в вершину j, и 0 - если нет. Для взвешенных графов вместо 1 хранят вес ребра.

• [+] Проверка "есть ли ребро (i, j)?" за O(1).
• [-] Память: O(N²) - расточительно для разреженных графов (мало ребер).
• [-] Перебор соседей вершины: O(N) - нужно пройти всю строку.

// Матрица смежности для неориентированного графа
#define MAX_V 100

int adj[MAX_V][MAX_V]; // Глобальный массив, инициализирован нулями
int n; // Количество вершин

void AddEdge(int u, int v) {
    adj[u][v] = 1;
    adj[v][u] = 1; // Для неориентированного графа
}

// Вывод всех соседей вершины v
void PrintNeighbors(int v) {
    for (int i = 0; i < n; i++) {
        if (adj[v][i]) printf("%d ", i);
    }
}

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

Для каждой вершины хранится список (массив или связный список) ее соседей. Это самый популярный способ представления на практике.

• [+] Память: O(N + M), где M - количество ребер. Идеально для разреженных графов.
• [+] Перебор соседей: за O(degree) - пропорционально степени вершины.
• [-] Проверка "есть ли ребро (i, j)?" за O(degree) - нужно пройти по списку.

// Список смежности на основе массивов (простейший вариант)
#define MAX_V 100
#define MAX_E 1000

// Для каждой вершины храним список соседей
int neighbors[MAX_V][MAX_V]; // neighbors[v][k] - k-й сосед вершины v
int degree[MAX_V];           // degree[v] - количество соседей вершины v

void AddEdge(int u, int v) {
    neighbors[u][degree[u]++] = v;
    neighbors[v][degree[v]++] = u; // Для неориентированного графа
}

// Вывод всех соседей вершины v
void PrintNeighbors(int v) {
    for (int i = 0; i < degree[v]; i++) {
        printf("%d ", neighbors[v][i]);
    }
}

3. Список ребер

Массив пар (u, v) - просто перечисление всех ребер графа.

• [+] Простейшая структура, минимальная память O(M).
• [+] Удобно для алгоритмов, работающих с ребрами (например, алгоритм Краскала).
• [-] Поиск соседей вершины: O(M) - нужно просмотреть все ребра.

// Список ребер
struct Edge {
    int u, v;    // Вершины, соединенные ребром
    int weight;  // Вес ребра (для взвешенных графов)
};

struct Edge edges[MAX_E];
int edgeCount = 0;

void AddEdge(int u, int v, int w) {
    edges[edgeCount].u = u;
    edges[edgeCount].v = v;
    edges[edgeCount].weight = w;
    edgeCount++;
}

Сравнение представлений