Перейти к содержанию

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

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