4624
правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Поиск в ширину''' (''Width (breadth) first search'') - метод обхода и разметки вершин графа...) |
KEV (обсуждение | вклад) Нет описания правки |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 1: | Строка 1: | ||
'''Поиск в ширину''' (''Width (breadth) first search'') | '''Поиск в ширину''' (''[[Width (breadth) first search]]'') — | ||
метод обхода и разметки вершин графа в следующем порядке: началу | метод [[обход графа|обхода]] и [[разметка вершин|разметки вершин]] [[граф|графа]] в следующем порядке: началу обхода <math>\,s</math> приписываем [[метка|метку]] <math>\,0,</math> [[смежные вершины|смежным с ней вершинам]] — метку <math>\,1.</math> | ||
обхода <math>s</math> приписываем метку 0, смежным с ней вершинам | Теперь рассматриваем поочередно ''[[окружение вершины|окружения]]'' всех вершин с метками | ||
Теперь рассматриваем поочередно ''окружения'' всех вершин с метками | <math>\,1</math> и каждой из входящих в эти окружения еще не занумерованных вершин | ||
1 и каждой из входящих в эти окружения еще не занумерованных вершин | приписываем метку <math>\,2</math> и т.д. Если исходный [[связный граф|граф связен]], то поиск в | ||
приписываем метку 2 и т.д. Если исходный граф связен, то поиск в | ширину пометит все его [[вершина|вершины]]. [[Дуга|Дуги]] вида <math>\,(i,i+1)</math> порождают остовный [[бесконтурный орграф]], содержащий в качестве своей части [[остовное дерево|остовное | ||
ширину пометит все его вершины. Дуги вида <math>(i,i+1)</math> порождают остовный | ордерево]], называемое ''[[поисковое дерево|поисковым деревом]]''. | ||
бесконтурный орграф, содержащий в качестве своей части остовное | |||
ордерево, называемое ''поисковым деревом''. | |||
Легко увидеть, что с помощью поиска в ширину | Легко увидеть, что с помощью поиска в ширину | ||
можно также занумеровать вершины, нумеруя вначале вершины с | можно также занумеровать вершины, нумеруя вначале вершины с | ||
меткой 1, затем с меткой 2 и т.д. | меткой <math>\,1,</math> затем с меткой <math>\,2</math> и т.д. | ||
Другое название | Другое название — ''[[Обход графа в ширину]]''. | ||
См. также ''Обход графа, Топологическая сортировка, Укладка уграфа'' | ==См. также == | ||
* ''[[Обход графа]],'' | |||
* ''[[Топологическая сортировка]],'' | |||
* ''[[Укладка уграфа]].'' | |||
==Литература== | ==Литература== | ||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. |