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

Ілюстрація пошуку у ширину. Чорні вершини пройдено, сірі чекають у черзі

По́шук у ширину́ — алгоритм пошуку на графі^[1].

Якщо задано граф G = (V, E) та початкову вершину s, алгоритм пошуку в ширину систематично обходить всі досяжні із s вершини. На першому кроці вершина s позначається, як пройдена, а в список додаються всі вершини, досяжні з s без відвідування проміжних вершин. На кожному наступному кроці всі поточні вершини списку відмічаються, як пройдені, а новий список формується із вершин, котрі є ще не пройденими сусідами поточних вершин списку. Для реалізації списку вершин найчастіше використовується черга та принцип FIFO. Виконання алгоритму продовжується до досягнення шуканої вершини або до того часу, коли на певному кроці в список не включається жодна вершина. Другий випадок означає, що всі вершини, доступні з початкової, уже відмічені, як пройдені, а шлях до цільової вершини не знайдений.

Алгоритм має назву пошуку в ширину, оскільки «фронт» пошуку (між пройденими та непройденими вершинами) одноманітно розширюється вздовж всієї своєї ширини. Тобто, алгоритм проходить всі вершини на відстані k перед тим як пройти вершини на відстані k+1.^[1]

Алгоритм

Наведемо кроки алгоритму

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

Формальний опис алгоритму

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

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

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);
}

Ітеративна формулювання:

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;                        // цільовий вузол недосяжний
}

Властивості

Позначимо число вершин і ребер в графі як $\vert V\vert$ і $\vert E\vert$ відповідно.

Просторова складність

Так як в пам'яті зберігаються всі розгорнуті вузли, просторова складність алгоритму становить $O(\vert V\vert +\vert E\vert )$ .

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

Часова складність

Так як в гіршому випадку алгоритм відвідує всі вузли графу, при зберіганні графу у вигляді списків суміжності^[en], тимчасова складність алгоритму становить $O(\vert V\vert +\vert E\vert )$ .

Повнота

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

Оптимальність

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

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

Джерела інформації

↑ ^а ^б Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 22.2: Пошук вшир. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.

Див. також

[mit-1] а ^б Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 22.2: Пошук вшир. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.

[1]