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

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

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

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

Зміст

АлгоритмРедагувати

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

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

ВластивостіРедагувати

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

Просторова складністьРедагувати

Так як в пам'яті зберігаються всі розгорнуті вузли, просторова складність алгоритму становить  .

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

Часова складністьРедагувати

Так як в гіршому випадку алгоритм відвідує всі вузли графа, при зберіганні графа у вигляді списків суміжності, тимчасова складність алгоритму становить  .

ПовнотаРедагувати

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

ОптимальністьРедагувати

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

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

Джерела інформаціїРедагувати

  1. а б Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). 22.2. Introduction to Algorithms (англ. ) (вид. 2-ге). MIT Press. с. 531. ISBN 0-262-03293-7. 

Див. такожРедагувати