Поиск в ширину

Материал из Википедии — свободной энциклопедии

Порядок обхода дерева в ширину

Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т. д.

[править] Реализация

Поиск в ширину реализуется с помощью структуры очередь. Для этого занесем в очередь исходную вершину. Затем будем работать, пока очередь не опустеет, таким образом: выберем элемент из очереди и добавим все смежные ему элементы, которые еще не использованы. Пример реализации на Паскале

push(start);
while not empty do
begin
  tek:=pop;  
  for i:=1 to n do 
    if (not used[a[tek,i]]) and (a[tek, i]<>0) then
    begin
      used[a[tek,i]]:=true;
      push(a[tek,i]);
    end;
end;

[править] Практические применения

• Волновой алгоритм в трассировке печатных плат;

[править] Ссылки

• http://pco.iis.nsk.su/grapp/WIN/sl_p.html

[править] Литература

• Ананий В. Левитин Глава 5. Метод уменьшения размера задачи: Поиск в ширину // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 215-218. — ISBN 0-201-74395-7
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1

Это незавершённая статья о компьютерах. Вы можете помочь проекту, исправив и дополнив её.

Это незавершённая статья по информатике. Вы можете помочь проекту, исправив и дополнив её.