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

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