Просмотр исходного текста страницы Поиск в глубину (DFS)

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

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

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

== Алгоритм DFS ==

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

== Реализация DFS ==

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

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

```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)
```

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

```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 ==

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

== Применение DFS ==

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

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

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

# '''Поиск цикла в графе''':

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

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

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

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

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

=== Недостатки: ===

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

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