Алгоритмы: Глубокий поиск

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

Основы

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

Порядок обхода дерева

Начиная с корневого узла (6), левая часть дерева исследуется на максимальную глубину, а затем исследуется правая. Обратите внимание, что эта логика продолжается и в дочерних узлах. Начиная с узла 8, левая сторона (8 -> 1 -> 3) исследуется раньше правой (8 -> 7).

Порядок обхода без дерева

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

Реализации

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

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

Проблема

Напишите алгоритм, который проверяет, существуют ли пути от корня к листьям, в которых сумма значений пути равна заданному значению «k».

class Node {
  constructor(val) {
    this.val = val
    this.left = null
    this.right = null
  }
}

Решение — рекурсивное

const hasPath = (node, k) => {
  if (node === null) return false

  if (node.left === null && 
      node.right === null && 
      node.val === k) {
        return true
  }
  return hasPath(node.left, k - node.val) || 
         hasPath(node.right, k - node.val)
}

Решение — итеративное

const hasPath = (node, k) => {
  const stack = [ [node, k ] ]

  while (stack.length > 0) {
    const [ node, target ] = stack.pop()

    if (node.left === null && node.right === null && node.val === target) {
      return true
    }

    if (node.right) {
      stack.push([node.right, target - node.val])
    }

    if (node.left) {
      stack.push([node.left, target - node.val])
    }
  }
  return false
}