Поиск в ширину: различия между версиями

'''Поиск в ширину''' (''[[Width (breadth) first search]]'') —

метод [[обход графа|обхода]] и [[разметка вершин|разметки вершин]] [[граф|графа]] в следующем порядке: началу обхода <math>\,s</math> приписываем [[метка|метку]] <math>\,0,</math> [[смежные вершины|смежным с ней вершинам]] — метку <math>\,1.</math>

Теперь рассматриваем поочередно ''[[окружение вершины|окружения]]'' всех вершин с метками

<math>\,1</math> и каждой из входящих в эти окружения еще не занумерованных вершин

приписываем метку <math>\,2</math> и т.д. Если исходный [[связный граф|граф связен]], то поиск в

ширину пометит все его [[вершина|вершины]]. [[Дуга|Дуги]] вида <math>\,(i,i+1)</math> порождают остовный [[бесконтурный орграф]], содержащий в качестве своей части [[остовное дерево|остовное

ордерево]], называемое ''[[поисковое дерево|поисковым деревом]]''.

меткой <math>\,1,</math> затем с меткой <math>\,2</math> и т.д.

Другое название — ''[[Обход графа в ширину]]''.

 

 

==См. также ==

* ''[[Обход графа]],''

* ''[[Топологическая сортировка]],''

* ''[[Укладка уграфа]].''

* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.