Закрепление материала: Графы

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

Суть урока. Мы познакомились с графами - универсальной структурой данных для моделирования связей. Разобрали три представления (матрица смежности, список смежности, список ребер) и два фундаментальных обхода - в глубину и в ширину. Проверим, насколько хорошо усвоен материал.

карта модуля о графах: три способа хранения графа и два обхода со своими структурами данных — Весь модуль на одной картинке: слева - чем хранить, справа - чем обходить

Краткое резюме модуля

В этом модуле мы заложили базу для работы со связными данными:

Граф G = (V, E) - структура, состоящая из множества вершин и множества ребер. Бывает ориентированным, неориентированным, взвешенным и невзвешенным.
Матрица смежности - представление графа в виде двумерного массива. Занимает O(N²) памяти, но обеспечивает проверку существования ребра за O(1). Идеально для плотных графов.
Список смежности - массив списков, где для каждой вершины хранится список ее соседей. Занимает O(N + M) памяти. Это самый популярный способ хранения, особенно для разреженных графов.
Поиск в глубину (Depth-First Search, DFS) - обход графа с использованием стека (или рекурсии). Алгоритм идет вглубь по ветви до тупика, затем возвращается назад.
Поиск в ширину (Breadth-First Search, BFS) - обход графа с использованием очереди. Алгоритм посещает вершины по уровням: сначала все соседи, затем соседи соседей. Находит кратчайший путь в невзвешенном графе.

Ключевые идеи

Главные концепции, определяющие выбор алгоритмов на графах:

Разреженность и плотность: выбор между списком и матрицей смежности напрямую зависит от количества ребер. Для графов, где количество ребер сильно меньше квадрата числа вершин, списки смежности экономят память.
Стек против очереди: фундаментальное различие двух обходов заключается в структуре данных, управляющей порядком обхода. LIFO (стек) дает обход в глубину, FIFO (очередь) - в ширину.
Компоненты связности: запуск обхода из одной вершины посещает только ту часть графа, в которую ведет путь. Запустив обход из всех непосещенных вершин по очереди, можно найти все изолированные компоненты связности.

Коротко: главное

Граф - универсальная структура для моделирования связей. Дерево - его частный случай.
Для разреженных графов используйте список смежности, для плотных - матрицу.
В глубину = стек, в ширину = очередь. Оба работают за время O(N + M).
Поиск в ширину гарантированно находит кратчайший путь в невзвешенном графе, поиск в глубину для этого не подходит.

Проверьте себя

Вопрос 1

Какую структуру данных использует поиск в глубину для хранения вершин, ожидающих обработки?

Очередь (queue) - принцип FIFO. Стек (stack) - принцип LIFO (или рекурсия). Приоритетную очередь (priority queue).

Вопрос 2

Дан разреженный граф: 10 000 вершин и 20 000 ребер. Какое представление будет наименее эффективным по памяти?

Матрица смежности - она займет O(N²) = 100 000 000 ячеек памяти. Список смежности - он займет O(N + M) памяти. Список ребер - он займет O(M) памяти.

Вопрос 3

Как с помощью базовых обходов найти все изолированные компоненты связности графа?

Достаточно запустить обход из вершины 0 - он обойдет весь граф. Отсортировать вершины по степени и группировать. Запускать обход из каждой еще непосещенной вершины - каждый запуск обходит одну компоненту.

Как вам урок? Спасибо за отзыв!