Задачи модуля "Графы": от матриц смежности до обходов

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

Суть урока. Практика - критерий истины. В этом уроке собраны проверочные вопросы и практическая задача на трассировку алгоритмов обхода графа.

Теоретические вопросы (Квиз)

Проверьте, насколько хорошо вы усвоили теоретическую часть модуля:

Вопрос 1

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

Массив массивов, список списков, хеш-таблица. Матрица смежности, список смежности, список ребер. Дерево отрезков, куча, бинарное дерево.

Вопрос 2

Что такое разреженный граф и какое представление для него наиболее эффективно?

Граф с малым числом ребер (|E| << |V|²). Наиболее эффективен список смежности. Граф с большим числом ребер (|E| ≈ |V|²). Наиболее эффективна матрица смежности. Граф, в котором отсутствуют циклы. Наиболее эффективен список ребер.

Вопрос 3

Объясните суть поиска в глубину (Depth-First Search). Какая структура данных лежит в его основе?

Обход по уровням: сначала все соседи. В основе лежит очередь. Обход по кратчайшим путям. В основе лежит Хеш-таблица. Обход идет "вглубь" по одной ветви до упора, затем возвращается назад. В основе лежит Стек (Stack).

Вопрос 4

Объясните суть поиска в ширину (Breadth-First Search). Для решения какой важной задачи он применяется в невзвешенном графе?

Поиск обходит граф случайными путями. Применяется для поиска Эйлерова цикла. Обход по уровням: сначала все соседи стартовой вершины, затем их соседи. Применяется для поиска кратчайшего пути. Идет вглубь графа по одному пути. Применяется для топологической сортировки.

Вопрос 5

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

Запустить обход из первой вершины; сколько соседей она имеет - столько и компонент. Пройти циклом по всем вершинам. Если вершина не посещена, увеличить счетчик компонент и запустить из нее обход, помечая достижимые вершины. Подсчитать количество листьев в дереве обхода в глубину.

Задача: Трассировка обходов

Дан следующий неориентированный граф (по сути, дерево):

неориентированный граф задачи из шести вершин: ребра A-B, A-C, B-D, B-E и C-F — Условие задачи: шесть вершин, пять ребер, обход начинается с вершины A

Задание 1: Напишите порядок посещения вершин при поиске в глубину, начиная с вершины A. При равном выборе соседей переходите к вершине, чья буква в алфавите идет раньше.

Задание 2: Напишите порядок посещения вершин при поиске в ширину, начиная с вершины A. Правило выбора соседей - то же.

Показать ответы

Поиск в глубину: A -> B -> D -> E -> C -> F
Объяснение: Из A идем в B (первый по алфавиту). Из B соседи D и E. Выбираем D. У D тупик, возвращаемся в B, идем в E. У E тупик, возвращаемся в B, затем в A. Из A идем в C, из C - в F.

Поиск в ширину: A -> B -> C -> D -> E -> F
Объяснение: На уровне 0: A. На уровне 1 (соседи A): B и C. На уровне 2 (соседи B и C): от B добавляются D и E, от C добавляется F.

разбор задачи: порядок обхода в глубину A, B, D, E, C, F и в ширину A, B, C, D, E, F — Оба ответа рядом: в глубину обход уходит по ветке до конца, в ширину снимает вершины уровень за уровнем

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