Обход графа

Дерево представляет отношение «один ко многим», в то время как граф обладает большей свободой и может представлять любые отношения «многие ко многим». Таким образом, мы можем рассматривать дерево как частный случай графа. Очевидно, что операция обхода дерева также является частным случаем операции обхода графа.

Как графы, так и деревья требуют применения алгоритмов поиска для выполнения операций обхода. Способы обхода графа также можно разделить на два типа: обход в ширину и обход в глубину.

Обход в ширину

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

Реализация алгоритма

BFS обычно реализуется с помощью очереди, код показан ниже. Очередь обладает свойством «первым пришел — первым вышел», что соответствует идее BFS «от ближайших к дальним».

Добавить начальную вершину обхода startVet в очередь и начать цикл.
В каждой итерации цикла извлечь вершину из начала очереди и записать посещение, затем добавить все смежные вершины этой вершины в конец очереди.
Повторять шаг 2. до тех пор, пока все вершины не будут посещены.

Чтобы предотвратить повторный обход вершин, необходимо использовать хеш-множество visited для записи того, какие узлы уже были посещены.

!!! tip

Хеш-множество можно рассматривать как хеш-таблицу, которая хранит только `key`, но не хранит `value`. Оно может выполнять операции добавления, удаления, поиска и изменения `key` за время $O(1)$. Благодаря уникальности `key`, хеш-множество обычно используется для удаления дубликатов данных и в других сценариях.

[file]{graph_bfs}-[class]{}-[func]{graph_bfs}

Код довольно абстрактный, рекомендуется сопоставить его с рисунком ниже для более глубокого понимания.

=== "<1>"

=== "<2>"

=== "<3>"

=== "<4>"

=== "<5>"

=== "<6>"

=== "<7>"

=== "<8>"

=== "<9>"

=== "<10>"

=== "<11>"

!!! question "Является ли последовательность обхода в ширину уникальной?"

Нет. Обход в ширину требует только порядка обхода «от ближайших к дальним», **а порядок обхода нескольких вершин на одинаковом расстоянии может быть произвольным**. Например, на рисунке выше порядок посещения вершин $1$, $3$ может быть изменен, порядок посещения вершин $2$, $4$, $6$ также может быть произвольным.

Анализ сложности

Временная сложность: Все вершины будут добавлены в очередь и извлечены из нее один раз, что требует O(|V|) времени; в процессе обхода смежных вершин, поскольку граф неориентированный, все ребра будут посещены 2 раза, что требует O(2|E|) времени; в целом используется O(|V| + |E|) времени.

Пространственная сложность: Список res, хеш-множество visited, очередь que могут содержать максимум |V| вершин, используя O(|V|) пространства.

Обход в глубину

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

Реализация алгоритма

Эта парадигма алгоритма «идти до конца и возвращаться» обычно реализуется на основе рекурсии. Подобно обходу в ширину, при обходе в глубину также необходимо использовать хеш-множество visited для записи посещенных вершин, чтобы избежать повторного посещения вершин.

[file]{graph_dfs}-[class]{}-[func]{graph_dfs}

Процесс алгоритма обхода в глубину показан на рисунке ниже.

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

Для более глубокого понимания рекомендуется объединить рисунок ниже с кодом и мысленно смоделировать (или нарисовать) весь процесс DFS, включая то, когда открывается и когда возвращается каждый рекурсивный метод.

=== "<1>"