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

Материал из WEGA
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Поиск в ширину''' (''[[Width (breadth) first search]]'') -
'''Поиск в ширину''' (''[[Width (breadth) first search]]'')
метод [[обход графа|обхода]] и [[разметка вершин|разметки вершин]] [[граф|графа]] в следующем порядке: началу обхода <math>s</math> приписываем [[метка|метку]] 0, [[смежные вершины|смежным с ней вершинам]] --- метку 1.
метод [[обход графа|обхода]] и [[разметка вершин|разметки вершин]] [[граф|графа]] в следующем порядке: началу обхода <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> и т.д.


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


==См. также ==
==См. также ==
''[[Обход графа]], [[Топологическая сортировка]], [[Укладка уграфа]]''.
* ''[[Обход графа]],''
* ''[[Топологическая сортировка]],''
* ''[[Укладка уграфа]].''
==Литература==
==Литература==
[Лекции],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


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

Версия от 13:13, 8 июня 2011

Поиск в ширину (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.