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

Поиск в ширину (Width (breadth) first search) - метод обхода и разметки вершин графа в следующем порядке: началу обхода [math]\displaystyle{ s }[/math] приписываем метку 0, смежным с ней вершинам --- метку 1. Теперь рассматриваем поочередно окружения всех вершин с метками 1 и каждой из входящих в эти окружения еще не занумерованных вершин приписываем метку 2 и т.д. Если исходный граф связен, то поиск в ширину пометит все его вершины. Дуги вида [math]\displaystyle{ (i,i+1) }[/math] порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом. Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т.д.

Другое название --- Обход графа в ширину.

См. также Обход графа, Топологическая сортировка, Укладка уграфа.

Литература

[Лекции],

[Евстигнеев-Касьянов/94]