2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа) — Подготовка к ЕГЭ/ОГЭ и сессии СПО и ВУЗы

Основные понятия графов

Граф — это математическая структура, состоящая из множества вершин (узлов) и множества рёбер (связей) между ними.

Основные термины:

Вершина (узел) — основной элемент графа
Ребро (дуга) — связь между двумя вершинами
Степень вершины — количество рёбер, инцидентных вершине
Путь — последовательность вершин, соединённых рёбрами
Цикл — путь, начинающийся и заканчивающийся в одной вершине

Виды графов

Графы можно классифицировать по различным признакам:

Тип графа	Описание	Пример
Неориентированный	Рёбра не имеют направления	Дороги между городами
Ориентированный	Рёбра имеют направление (дуги)	Одностороннее движение
Взвешенный	Рёбрам присвоены числовые значения (веса)	Расстояния между городами
Не взвешенный	Рёбра не имеют весов	Социальные связи
Связный	Между любыми двумя вершинами существует путь	Дерево
Несвязный	Имеются изолированные компоненты	Острова
Ациклический	Не содержит циклов	Дерево, направленный ациклический граф (DAG)

Пример ориентированного ациклического графа (DAG):

Этот граф ориентированный и не содержит циклов.

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

Матрица смежности — это квадратная матрица, показывающая связи между вершинами графа.

Для графа с n вершинами матрица смежности имеет размер n × n, где элемент a[i][j] равен:

1 (или весу ребра) — если есть ребро из вершины i в вершину j
0 — если ребра нет

Пример графа и его матрицы смежности:

1

2

3

1

0

1

2

1

0

1

3

1

0

Особенности матрицы смежности:

Для неориентированных графов матрица симметрична относительно главной диагонали
Для ориентированных графов матрица может быть несимметричной
Занимает много памяти для разреженных графов (\(O(n^2)\))
Быстрый доступ к наличию ребра между вершинами (\(O(1)\))

Весовые матрицы

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

Пример взвешенного графа и его матрицы:

A

B

C

A

0

5

3

B

5

0

7

C

3

7

0

Примечание: Если ребра между вершинами нет, в весовой матрице обычно указывают:

0 — если вес может быть только положительным
∞ (бесконечность) — если возможны отрицательные веса

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

Список смежности — это структура данных, где для каждой вершины хранится список смежных с ней вершин.

Пример графа и его списка смежности:

Преимущества и недостатки списков смежности:

Экономия памяти для разреженных графов (\(O(n + m)\))
Быстрое получение всех соседей вершины
Медленная проверка наличия ребра между вершинами (\(O(deg(v))\))

Построение оптимального пути между вершинами

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

Алгоритм Дейкстры:

Присвоить начальной вершине вес 0, а всем остальным — бесконечность
Поместить все вершины в непосещённые
Пока есть непосещённые вершины:
- Выбрать вершину с минимальным весом
- Обновить веса её соседей
- Пометить вершина как посещённую

Пример работы алгоритма Дейкстры:

                        // Находим кратчайший путь от A до D

                        Шаг 1: A(0), B(∞), C(∞), D(∞)

                        Шаг 2: Посещаем A, обновляем B=2, C=1

                        Шаг 3: Посещаем C, обновляем D=1+3=4

                        Шаг 4: Посещаем B, обновляем D=min(4, 2+5)=4

                        Кратчайший путь: A→C→D (длина 4)

Определение количества путей в ориентированном ациклическом графе

Для ориентированного ациклического графа (DAG) можно эффективно посчитать количество путей между вершинами.

Алгоритм:

Выполнить топологическую сортировку вершин
Присвоить начальной вершине значение 1 (один путь)
Для каждой последующей вершины в порядке топологической сортировки:
- Установить количество путей равным сумме путей всех предшественников

Пример подсчёта количества путей:

                        Топологический порядок: A, B, C, D

                        paths[A] = 1

                        paths[B] = paths[A] = 1

                        paths[C] = paths[A] = 1

                        paths[D] = paths[B] + paths[C] = 1 + 1 = 2

                        Количество путей от A до D: 2

Практические рекомендации

При решении задач с графами:

Выбирайте подходящее представление графа в зависимости от задачи
Для плотных графов используйте матрицы смежности
Для разреженных графов используйте списки смежности
Для поиска кратчайших путей во взвешенных графах применяйте алгоритм Дейкстры
Для подсчёта путей в DAG используйте топологическую сортировку

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

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

                        int graph[V][V] = {

                          {0, 1, 1, 0},

                          {1, 0, 1, 1},

                          {1, 1, 0, 1},

                          {0, 1, 1, 0}

                        };

                        // Список смежности для разреженного графа

                        vector<list<int>> graph(V);

                        graph[0].push_back(1);

                        graph[0].push_back(2);

                        graph[1].push_back(0);

                        graph[1].push_back(2);

                        graph[1].push_back(3);

                        // …

Графы: основные понятия и представление