Дерево
Поиск в глубину
Описание
Поиск в глубину (depth-first search, DFS) - один из методов обхода дерева или графа. Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти "вглубь" графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины ребра. Если ребро ведет в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать ребра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось ребер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин.
Сложность
Временная сложность данного алгоритма составляет O(n), поскольку мы должны посетить все узлы и делаем это один раз.
Реализация
Реализация данного алгоритма не отличается большой сложностью:
// algorithms/trees/depth-first-search.js
// Функция инициализации обработчиков
function initCallbacks(callbacks = {}) {
const initiatedCallbacks = {}
const stubCallback = () => {}
const defaultAllowTraverseCallback = () => true
// Обработчик определения допустимости обхода
initiatedCallbacks.allowTraverse =
callbacks.allowTraverse || defaultAllowTraverseCallback
// Обработчик вхождения в узел
initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback
// Обработчик выхода из узла
initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback
return initiatedCallbacks
}
// Функция принимает узел и обработчики
function depthFirstSearchRecursive(node, callbacks) {
// Вызываем обработчик вхождения в узел
callbacks.enterNode(node)
// Если имеется левый узел и его обход разрешен
if (node.left && callbacks.allowTraverse(node, node.left)) {
// Обходим левое поддерево
depthFirstSearchRecursive(node.left, callbacks)
}
// Если имеется правый узел и его обход разрешен
if (node.right && callbacks.allowTraverse(node, node.right)) {
// Обходим правое поддерево
depthFirstSearchRecursive(node.right, callbacks)
}
// Вызываем обработчик выхода из узла
callbacks.leaveNode(node)
}
// Функция принимает начальный (корневой) узел и обработчики
export default function depthFirstSearch(root, callbacks) {
// Инициализируем обработчики
const _callbacks = initCallbacks(callbacks)
// Запускаем рекурсию
depthFirstSearchRecursive(root, _callbacks)
}
Тесты
Поиск в ширину
Описание
Поиск в ширину (breadth-first search, BFS) - один из методов обхода графа. Пусть задан граф G=(V,E) и выделена исходная вершина s. Алгоритм поиска в ширину систематически обходит все ребра G для "открытия" всех вершин, достижимых из s, вычисляя при этом расстояние (минимальное количество ребер) от s до каждой достижимой вершины.
Поиск в ширину имеет такое название потому, что в процессе обхода мы идем вширь, то есть перед тем как приступить к поиску вершин на расстоянии k+1, выполняется обход вершин на расстоянии k.
Сложность
Временная сложность данного алгоритма составляет O(n), поскольку мы должны посетить все узлы и делаем это один раз.
Реализация
Для реализации данного алгоритма воспользуемся такой структурой данных, как очередь (queue):
// algorithms/trees/breadth-first-search.js
import Queue from '../../data-structures/queue'
// Функция инициализации обработчиков
function initCallbacks(callbacks = {}) {
const initiatedCallbacks = {}
const stubCallback = () => {}
const defaultAllowTraverseCallback = () => true
// Обработчик определения допустимости обхода
initiatedCallbacks.allowTraverse =
callbacks.allowTraverse || defaultAllowTraverseCallback
// Обработчик вхождения в узел
initiatedCallbacks.enterNode = callbacks.enterNode || stubCallback
// Обработчик выхода из узла
initiatedCallbacks.leaveNode = callbacks.leaveNode || stubCallback
return initiatedCallbacks
}
// Функция принимает начальный (корневой) узел и обработчики
export default function breadthFirstSearch(root, callbacks) {
// Инициализируем обработчики
const _callbacks = initCallbacks(callbacks)
// Создаем очередь
const queue = new Queue()
// Добавляем корневой узел в конец очереди
queue.enqueue(root)
// Пока в очереди есть элементы
while (!queue.isEmpty()) {
// Берем узел из начала очереди
const node = queue.dequeue()
// Вызываем обработчик вхождения в узел
_callbacks.enterNode(node)
// Если имеется левый узел и его обход разрешен
if (node.left && _callbacks.allowTraverse(node, node.left)) {
// Добавляем его в конец очереди
queue.enqueue(node.left)
}
// Если имеется правый узел и его обход разрешен
if (node.right && _callbacks.allowTraverse(node, node.right)) {
// Добавляем его в конец очереди
queue.enqueue(node.right)
}
// Вызываем обработчик выхода в узел
_callbacks.leaveNode(node)
}
}
Тесты
Запускаем тесты:
npm run test ./algorithms/trees/__tests__
