Поиск в ширину

Width (breadth) first search

метод обхода и разметки вершин графа в следующем порядке: началу обхода s приписываем метку 0, смежным с ней вершинам - метку 1. Теперь рассматриваем поочередно окружения всех вершин с метками 1 и каждой из входящих в эти окружения еще не занумерованных вершин приписываем метку 2 и т.д. Если исходный граф связен, то поиск в ширину пометит все его вершины. Дуги вида  порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом. Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т.д. Другое название - Обход графа в ширину. См. также Обход графа, Топологическая сортировка, Укладка уграфа.

Литература: [Лекции], [Евстигнеев-Касьянов/94] .