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

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


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


См. также ''Обход графа, Топологическая сортировка, Укладка уграфа''.
==См. также ==
''[[Обход графа]], [[Топологическая сортировка]], [[Укладка уграфа]]''.
==Литература==
==Литература==
[Лекции],  
[Лекции],  


[Евстигнеев-Касьянов/94]
[Евстигнеев-Касьянов/94]

Версия от 11:59, 21 декабря 2009

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

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

См. также

Обход графа, Топологическая сортировка, Укладка уграфа.

Литература

[Лекции],

[Евстигнеев-Касьянов/94]