Реверсивный поиск и перебор поддеревьев графа

Abstract

Реверсивный поиск – один из алгоритмов, идея которого «витает в воздухе» десятилетиями и который часто изобретается заново программистами, знакомыми с такими алгоритмами, как поиск в ширину (BFS) и поиск в глубину (DFS). В 1996 г. алгоритму было дано имя и довольно общая формулировка [1], с которой его можно применить ко множеству различных задач. В статье показано ещё одно применение этого алгоритма – перебор поддеревьев произвольного графа.