Поиск в глубину (DFS) — различия между версиями

Текущая версия на 17:51, 8 марта 2025

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

Основные понятия

1. Граф (Graph): Структура данных, состоящая из множества вершин (узлов) и множества ребер, соединяющих эти вершины.
2. Вершина (Vertex): Узел графа.
3. Ребро (Edge): Соединение между двумя вершинами графа.
4. Стек (Stack): Структура данных, основанная на принципе LIFO (Last In, First Out), используемая для хранения информации о вершинах, которые необходимо посетить.
5. Посещенная вершина (Visited Vertex): Вершина, которая уже была обработана алгоритмом DFS.
6. Непосещенная вершина (Unvisited Vertex): Вершина, которая еще не была обработана алгоритмом DFS.
7. Корень (Root): Вершина, с которой начинается обход графа.
8. Время входа (Discovery Time): Момент времени, когда вершина была впервые посещена алгоритмом DFS.
9. Время выхода (Finish Time): Момент времени, когда все смежные с вершиной вершины были посещены, и алгоритм DFS возвращается к предыдущей вершине.

Алгоритм DFS

1. Отметить корень как посещенный. 2. Для каждой непосещенной вершины $u$, смежной с корнем:

  *  Рекурсивно вызвать DFS для вершины $u$.

Реализация DFS

Существуют два основных способа реализации DFS: рекурсивный и итеративный (с использованием стека).

1. 1. 1. Рекурсивная реализация:

```python def depth_first_search_recursive(graph, vertex, visited=None):

   if visited is None:
       visited = set()
   visited.add(vertex)
   print(vertex, end=" ")  # Обработка вершины (посещение)

   for neighbor in graph[vertex]:
       if neighbor not in visited:
           depth_first_search_recursive(graph, neighbor, visited)

```

1. 1. 1. Итеративная реализация (с использованием стека):

```python def depth_first_search_iterative(graph, start_vertex):

   visited = set()
   stack = [start_vertex]

   while stack:
       vertex = stack.pop()
       if vertex not in visited:
           visited.add(vertex)
           print(vertex, end=" ")  # Обработка вершины (посещение)

           # Добавляем соседей в стек в обратном порядке, чтобы они были обработаны в правильном порядке
           neighbors = list(graph[vertex])
           neighbors.reverse()
           stack.extend(neighbors)

```

Пример графа в виде списка смежности:

```python graph = {

   0: [1, 2],
   1: [0, 3, 4],
   2: [0, 5],
   3: [1],
   4: [1],
   5: [2]

} ```

Вызов рекурсивной реализации:

```python print("DFS (Recursive):", end=" ") depth_first_search_recursive(graph, 0) print() ```

Вызов итеративной реализации:

```python print("DFS (Iterative):", end=" ") depth_first_search_iterative(graph, 0) print() ```

Свойства DFS

1. Временная сложность: $O(V + E)$, где $V$ — количество вершин, $E$ — количество ребер.
2. Пространственная сложность: $O(V)$, в худшем случае стек может содержать все вершины графа.
3. Не гарантирует нахождение кратчайшего пути: DFS не гарантирует нахождение кратчайшего пути между двумя вершинами.

Применение DFS

DFS используется в широком спектре приложений, включая:

1. Поиск всех достижимых вершин из заданной вершины: DFS позволяет найти все вершины, которые достижимы из заданной вершины.
2. Проверка связности графа: DFS можно использовать для проверки, является ли граф связным.
3. Поиск цикла в графе: DFS можно использовать для поиска цикла в графе.
4. Топологическая сортировка: DFS используется для топологической сортировки ориентированного ациклического графа (DAG).
5. Поиск компонентов сильной связности: DFS используется для поиска компонентов сильной связности ориентированного графа.
6. Решение лабиринтов: DFS можно использовать для поиска пути в лабиринте.

Примеры использования DFS

1. Поиск цикла в графе:

1. 1. DFS можно использовать для определения, содержит ли граф цикл. Если во время обхода DFS встречается вершина, которая уже была посещена, то это означает, что в графе есть цикл.
2. Топологическая сортировка:

1. 1. Топологическая сортировка — это упорядочение вершин ориентированного ациклического графа (DAG) таким образом, что для каждого ребра $(u, v)$ вершина $u$ появляется в упорядочении раньше вершины $v$. DFS можно использовать для выполнения топологической сортировки.

Преимущества и недостатки использования DFS

Преимущества:

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

Недостатки:

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

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