Редагування Пошук у ширину

[[Файл:Breadth-first-tree.svg|thumb|right|250px|Порядок обходу вершин.]]
[[Файл:Animated BFS.gif|thumb|right|250px|Ілюстрація пошуку у ширину. Чорні вершини пройдено, сірі чекають у черзі]]
'''По́шук у ширину́'''&nbsp;— [[алгоритм]] пошуку на [[граф (математика)|графі]].<ref name="mit">{{cite book
|автор=''Thomas H. Cormen'', ''Charles E. Leiserson'', ''Ronald L. Rives''t, ''Clifford Stein''
|рік=2001
|назва=Introduction to Algorithms
| розділ=22.2
|видання=2-ге
|мова={{lang-en|}}
|сторінки=531
|видавництво=MIT Press
|isbn=0-262-03293-7}} </ref>

Якщо задано граф ''G'' = (''V'',&nbsp;''E'') та початкову вершину ''s'', алгоритм пошуку в ширину систематично обходить всі досяжні із ''s'' вершини. На першому кроці вершина ''s'' позначається, як пройдена, а в список додаються всі вершини, досяжні з ''s'' без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується [[Черга (структура даних)|черга]] та принцип [[Алгоритм заміщення комірок пам’яті FIFO|FIFO]]. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений. 
 
Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані ''k'' перед тим як пройти вершини на відстані ''k''+1.<ref name="mit" />

== Алгоритм ==
Наведемо кроки алгоритму
# Почати з довільної вершини v. Виконати BFS(v):=1. Включити вершину v у чергу.
# Розглянути вершину, яка перебуває на початку черги; нехай це буде вершина х. Якщо для всіх вершин, суміжних із вершиною х, уже визначено BFS-номери, то перейти до кроку 4, інакше - до кроку 3.
# Нехай {x,y} - ребро, у якому номер BFS(у) не визначено. Позначити це ребро потовщеною суцільною лінією, визначити BFS(у) як черговий BFS-номер, включити вершину у чергу й перейти до кроку 2.
# Виключити вершину х із черги. Якщо черга порожня, то зупинитись, інакше - перейти до кроку 2.

== Формальний опис алгоритму ==
Нижче наведено [[псевдокод]] алгоритму для випадку, коли необхідно лише знайти цільовий вузол. Залежно від конкретного застосування алгоритму, може знадобитися додатковий код, що забезпечує збереження потрібної інформації (відстань від початкового вузла, вузол-батько і т. п.)

Рекурсивна формулювання:<syntaxhighlight>

BFS(start_node, goal_node) {
  return BFS'({start_node}, ∅, goal_node);
}
BFS'(fringe, visited, goal_node) {
  if(fringe == ∅) {
    // цільовий вузол не знайдено
    return false; 
  }
  if (goal_node ∈ fringe) {
    return true;
  }
  return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node);
}
</syntaxhighlight>Ітеративна формулювання:<syntaxhighlight>
BFS(start_node, goal_node) {
 for(all nodes i) visited[i] = false; // спочатку список відвіданих вузлів порожній
 queue.push(start_node);              // починаючи з вузла-джерела
 visited[start_node] = true;
 while(! queue.empty() ) {            // поки черга не порожня
  node = queue.pop();                 // витягти перший елемент в черзі
  if(node == goal_node) {
   return true;                       // перевірити, чи не є поточний вузол цільовим
  }
  foreach(child in expand(node)) {    // всі наступники поточного вузла, ...
   if(visited[child] == false) {      // ... які ще не були відвідані ...
    queue.push(child);                // ... додати в кінець черги...
    visited[child] = true;            // ... і позначити як відвідані
   }
  }
 }
 return false;                        // цільовий вузол недосяжний
}
</syntaxhighlight>

== Властивості ==
Позначимо число вершин і ребер в графі як <math> \vert V \vert </math> і <math> \vert E \vert </math> відповідно.

=== Просторова складність ===
Так як в пам'яті зберігаються всі розгорнуті вузли, [[Теорія складності обчислень|просторова складність]] алгоритму становить <math>O(\vert V \vert + \vert E \vert)</math>.

Алгоритм пошуку з ітеративним поглибленням схожий на пошук в ширину тим, що при кожній ітерації перед переходом на наступний рівень досліджується повний рівень нових вузлів, але вимагає значно менше пам'яті.

=== Часова складність ===
Так як в гіршому випадку алгоритм відвідує всі вузли графа, при зберіганні графа у вигляді списків [[Матриця суміжності|суміжності]], [[Теорія складності обчислень|тимчасова складність]] алгоритму становить <math>O(\vert V \vert + \vert E \vert)</math>.

=== Повнота ===
Якщо у кожного вузла є кінцеве число наступників, алгоритм є повним: якщо рішення існує, алгоритм пошуку в ширину його знаходить, незалежно від того, чи є граф кінцевим. Однак якщо рішення не існує, на нескінченному графі пошук не закінчується.

=== Оптимальність ===
Якщо довжини ребер графа рівні між собою, пошук в ширину є оптимальним, тобто завжди знаходить найкоротший шлях. В разі зваженого графа пошук в ширину знаходить шлях, що містить мінімальну кількість ребер, але не обов'язково найкоротший.

Пошук за критерієм вартості є узагальненням пошуку в ширину і оптимальний на зваженому графі з невід'ємними вагами ребер. Алгоритм відвідує вузли графа в порядку зростання вартості шляху з початкового вузла і зазвичай використовує чергу з пріоритетами.

== Джерела інформації ==
<references />

== Див. також ==
{{Алгоритми пошуку графами}}

* [[Список алгоритмів]]
* [[Обхід дерева]]
* [[Пошук в глибину]]
* [[Пошук за критерієм вартості]]
* [[Двонаправлений пошук]]
* [[Теорія графів]]

[[Категорія:Алгоритми на графах]]
[[Категорія:Алгоритми пошуку]]