Как работает обход графа в глубину?

Что такое обход в глубину?

Обход в глубину (Depth-First Search, DFS) — это алгоритм для обхода или поиска в структурах данных, таких как графы и деревья. Он начинает с выбранной начальной вершины и рекурсивно или итеративно исследует каждую ветвь до конца, прежде чем вернуться назад. Это контрастирует с обходом в ширину (BFS), который исследует все вершины на текущем уровне перед переходом на следующий.

Как работает DFS?

Алгоритм использует стек для запоминания вершин, которые нужно посетить. В рекурсивной реализации стек создается автоматически вызовами функций. Основные шаги:

• Пометить текущую вершину как посещенную.
• Для каждого соседа, который еще не посещен, рекурсивно вызвать DFS.
• Когда все соседи обработаны, вернуться к предыдущей вершине.

Пример реализации на JavaScript

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  console.log(start);
  for (const neighbor of graph[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

dfs(graph, 'A'); // A, B, D, E, F, C

Применение DFS

DFS используется во многих задачах:

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

Вывод

DFS — это фундаментальный алгоритм для работы с графами, который эффективен для глубокого исследования структуры. Его стоит применять, когда нужно найти все возможные пути или проверить свойства графа, особенно если граф не слишком широкий.