Медведев Михаил Геннадиевич
Кандидат физико-математических наук, доцент факультета кибернетики Киевского национального университета имени Тараса Шевченко.
Поиск в глубину на графе
Многие практические задачи описываются как задачи обхода некоторого лабиринта с целью вычисления определённых его свойств. Математическая абстракция, соответствующая лабиринту, называется графом. Граф – это множество точек (комнат), соединённых рёбрами (проходами между комнатами).
В этой статье мы рассмотрим один из основных алгоритмов на графе – поиск в глубину, а вместе с ним технику разметки и раскраски вершин.