… введение

Поиск в глубину (DFS) - это алгоритм обхода или поиска структур данных в виде дерева или графа. Алгоритм начинается с корневого узла (выбирая некоторый произвольный узел в качестве корневого узла в случае графа) и исследует, насколько это возможно, вдоль каждой ветви перед обратным отслеживанием.

Прежде чем продолжить, давайте формально определим граф и некоторые из его компонентов;

Узел (также называемый вершиной): это фундаментальная часть всех графов. Он может иметь имя (ключ), а также может содержать дополнительную информацию (полезные данные).

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

Следовательно, график может быть представлен как G, где G = (V, E) .

Для графа G, V - это набор вершин, а E - это набор ребер.

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

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

Псевдокод;

1  Initialize an empty stack for storage of nodes, S.
2  For each vertex u, define u.visited to be false.
3  Push the root (first node to be visited) onto S.
4  While S is not empty:
5   Pop the first element in S, u.
6   If u.visited = false, then:
7      U.visited = true
8      for each unvisited neighbor w of u:
9         Push w into S.
10 End process when all nodes have been visited.

Реализация Python с использованием рекурсии.


1 def depth_first_search_recursive(graph, start, visited=None):
2    if visited is None:
3        visited = set()
4    visited.add(start)
5    for next in graph[start] - visited:
6        depth_first_search_recursive(graph, next, visited)
7    return visited

Поиск в глубину посещает каждый узел один раз и проверяет каждое ребро графа один раз. Следовательно, сложность DFS равна O (V + E). Это предполагает, что граф представлен как список смежности.

Прочтите более подробную информацию о поиске в глубину здесь.