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