Перейти к содержанию
Приглашаем вас участвовать в развитии русской версии! Подробнее здесь.

# 9.5 Упражнения

## 9.5.1 Вопросы для самопроверки

### 1. Два представления одного графа

Неориентированный граф содержит 4 вершины `A, B, C, D` и ребра `A-B, A-C, B-C, C-D`.

1. Запишите его список смежности.
2. Заполните матрицу смежности, содержащую только 0 и 1.
3. Какое представление графа позволяет определить, соединены ли напрямую `A` и `D`, просмотрев лишь один элемент хранилища?
4. Какое представление обычно экономнее по памяти, если в графе много вершин, но мало ребер?

Ответ

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

       A: B, C
       B: A, C
       C: A, B, D
       D: C

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

   | A | B | C | D
   --- | --- | --- | --- | ---
   A | 0 | 1 | 1 | 0
   B | 1 | 0 | 1 | 0
   C | 1 | 1 | 0 | 1
   D | 0 | 0 | 1 | 0

3. В матрице смежности достаточно посмотреть ячейку на пересечении строки `A` и столбца `D`, поэтому она удобна для проверки прямой связи любой пары вершин.

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

### 2. Порядок обхода в ширину и в глубину

Неориентированный граф содержит вершины `A, B, C, D, E` и ребра `A-B, A-C, B-D, C-D, D-E`.

Начните с A и при наличии нескольких непосещенных смежных вершин выбирайте их в алфавитном порядке.

1. Запишите порядок обхода в ширину (BFS).
2. Запишите порядок рекурсивного обхода в глубину (DFS).
3. Почему при обоих обходах необходимо отмечать уже посещенные вершины?

Ответ

1. Порядок BFS: `A, B, C, D, E`. Сначала посещаются B и C, отстоящие от A на одно ребро, а затем более далекие D и E.

2. Порядок DFS: `A, B, D, C, E`. Обход последовательно переходит в непосещенную смежную вершину текущей вершины, поэтому сначала проходит путь `A → B → D → C`. Когда у C не остается новых смежных вершин, обход возвращается к D и посещает E.

3. В графе есть цикл, например `A-B-D-C-A`. Если не отмечать посещенные вершины, обход может снова и снова проходить по циклу через одни и те же вершины и не завершиться.

### 3. Можно ли посетить весь граф за один BFS

Неориентированный граф содержит вершины `A, B, C, D, E, F` и только ребра `A-B, B-C, D-E`.

1. Какие вершины можно посетить за один BFS, начав с A?
2. Посещены ли после этого все вершины графа? Почему?
3. Если перебирать все вершины в алфавитном порядке и запускать новый BFS при каждой непосещенной вершине, какие вершины станут начальными для отдельных запусков? На сколько несвязанных частей (компонент связности) разделен граф?

Ответ

1. Из A можно посетить только `A, B, C`.

2. Не все вершины посещены. `D, E` образуют другую связную часть, а F — отдельная вершина; путей от A до них нет, поэтому из A они недостижимы.

3. Начальными вершинами трех запусков BFS будут последовательно `A, D, F`; они посетят `{A, B, C}`, `{D, E}` и `{F}` соответственно. Следовательно, граф содержит 3 компоненты связности.

## 9.5.2 Задачи по программированию

### 1. Проверка существования пути в неориентированном графе

Дан неориентированный граф из \(n\) вершин, пронумерованных от \(0\) до \(n-1\). Каждый элемент `[u, v]` массива `edges` обозначает неориентированное ребро между вершинами `u` и `v`.

Также даны начальная вершина `source` и конечная вершина `destination`. Сначала постройте по `edges` список смежности, а затем с помощью BFS или DFS определите, существует ли путь от `source` до `destination`: если существует, верните `true`, иначе — `false`. Граф может содержать циклы и быть несвязным.

Подсказки

1. Каждое неориентированное ребро нужно добавить в обоих направлениях
2. Граф может содержать циклы, поэтому обязательно отмечайте уже посещенные вершины
3. Начните с source: встретив destination, верните true; если обход завершился без нее, верните false

LeetCode

##### Оставляйте свои идеи, вопросы и предложения в комментариях