Изучим обход графа с помощью алгоритмов DFS и BFS.

В моем последнем учебнике я обсуждал некоторые фундаментальные знания о графах. Сегодня я расскажу об использовании двух известных алгоритмов обхода графа или дерева. За свою профессиональную карьеру я ни разу не сталкивался с ситуацией, когда мне приходилось реализовывать алгоритмы обхода графа. Тем не менее, если вы готовитесь к собеседованию при приеме на работу или интересуетесь некоторыми основами информатики, вам следует знать эти два алгоритма.

Мы можем применить оба этих алгоритма для обхода графов и деревьев.

  1. DFS — Поиск в глубину
  2. BFS — поиск в ширину

1. DFS — поиск в глубину

Алгоритм DFS начинается с вершины и завершает посещение ветви, прежде чем перейти к другим ветвям. Перемещение DFS начинается с A → B → E → K → F → C и продолжается в следующей анимации.

Вот простой граф из пяти узлов. Но в этом графе узлы D и E не связаны с узлами A, B и C. Давайте представим этот граф в реальном коде и пройдемся по нему.

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

Давайте создадим граф, используя представление списка смежности. Сначала определите структуру узла в Swift. Здесь мы будем называть каждый узел вершиной.

Каждая вершина имеет

  • keyкоторый может быть любого типа
  • Логическая переменная visited
  • Массив adjacent, чтобы знать, какие другие вершины связаны

Строки 17–27 используются для установления соединений между узлами.

Давайте определим алгоритм DFS. Здесь мы будем следовать рекурсивному способу посещения подключенных узлов из начального узла. Мы вызовем функцию dfs и передадим узел a., чтобы начать обход.

Вывод:

A
B
C

Поскольку A → B → C связан, мы вызываем функцию dfs и передаем узел a в качестве корневого узла. Вершины D и E не печатаются, так как они не связаны с вершинами A, B и C.

Анализ:

Runtime: O(V+E) where V and E are the vertices
Space: O(h) height of the recursion stack
  • visit — это функция, которая печатает ключ
  • Функция dfs сначала проверяет, является ли root допустимым узлом или нет
  • Если root является допустимым узлом, он посещает узел и отмечает посещенный узел.
  • Затем он запускает цикл для проверки каждого соседнего узла корневого узла.
  • Если какой-либо из узлов не посещается, он рекурсивно вызывает ту же функцию dfs для этого соседнего узла.

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

Представим тот же граф с помощью матрицы смежности. И определите другую функцию DFS.

Вывод:

A
B
C

Анализ:

Time: O(V^2) - where V is the number of vertices and as it is represented by a matrix
Space: O(n+h) 
 - n is the number of vertices stored in a set and 
 - h is the height of the recursion stack
  • Здесь dfs тоже рекурсивная функция, как и раньше
  • Поскольку мы использовали матрицу для представления графа, мы использовали структуру данных Set, чтобы определить, посещается ли вершина или нет. Для этой цели мы также можем использовать структуру данных словаря.
  • Единственная разница заключается в цикле for и внутри цикла.
  • Цикл работает от 0 до количества столбцов
  • Если корневой узел не является ребром, если в матрице позиционное значение ребра равно 1, и если вершина не входит в множество, то мы рекурсивно вызываем функцию dfs и передаем ребро как корневой узел

Рекурсивный — это распространенный способ реализации алгоритма DFS. Теперь давайте обсудим алгоритм BFS.

2. BFS — поиск в ширину

Алгоритм BFS начинается с вершины и сначала посещает всех соседей, прежде чем перейти к их потомкам. В следующей анимации перемещение BFS начинается с A → B → C → D → E → F… и продолжается.

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

Используя список смежности, давайте определим граф A → B → C → D → E.

Давайте определим функцию BFS.

Выход:

A B C

Анализ:

Runtime: O(V+E)
Space: O(V)
  • Основное различие между алгоритмами DFS и BFS заключается в том, что в алгоритме BFS используется queue структура данных.
  • В Swift нет встроенной структуры данных queue. Итак, здесь мы использовали массив для представления очереди для простоты
  • Итак, сначала мы добавляем корневой узел в очередь и помечаем его как посещенный.
  • Затем мы запускаем цикл while, пока очередь не станет пустой.
  • Внутри цикла while мы берем первую вершину из очереди и посещаем ее.
  • Мы запускаем цикл for для извлечения каждого ребра из соседней вершины.
  • Если ребро не посещено, мы добавляем его в очередь и помечаем как посещенное

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

Используя матрицу смежности, давайте представим тот же граф и определим другую функцию bfs.

Выход:

A
B
C

Анализ:

Runtime: O(V+E)
Space: O(V+V) // Queue + Set
  • Алгоритм почти такой же, как у предыдущей bfsfunction
  • Чтобы отметить посещенные узлы, мы использовали структуру данных набора visited внутри функции bfs.
  • Другая часть - это просто настройка для проверки матрицы на обход

Итак, я надеюсь, вы поняли, как работают DFS и BFS. Вы можете попробовать применить свои знания для решения некоторых проблем leetcode с DFS и BFS.

Проблемы DFS:https://leetcode.com/tag/depth-first-search/

Проблемы BFS:https://leetcode.com/tag/breadth-first-search/