Хвильовий алгоритм

Алгоритм пошуку в ширину (англ. Breadth-first search, BFS) дозволяє знайти найкоротші шляхи з однієї вершини незваженого (орієнтованого або неорієнтованого) графа до всіх інших вершин. Під найкоротшим шляхом мається на увазі шлях, що містить найменшу кількість ребер.

Нехай до вершини u знайдена найкоротша відстань і вона дорівнює d, а до вершини v найкоротша відстань не менше, ніж d. Тоді якщо вершини u і v - суміжні, то найкоротша відстань до вершини v дорівнює d + 1.

Через d [i] будемо позначати найкоротшу відстань до вершини i. Нехай початкова вершина має номер s, тоді d [s] = 0. Для всіх вершин суміжних з s відстань дорівнює 1. Для вершин, суміжних з тими, до яких відстань дорівнює 1, відстань дорівнює 2 (якщо тільки вона не дорівнює 0 або 1) і т. д. \

Хвильовий алгоритм здійснює процес обчислення найкоротших відстаней до вершин таким чином.

Для кожної вершини в масиві d будемо зберігати найкоротшу відстань до цієї вершини, якщо ж відстань невідома - будемо вважати її нескінченою.

На самому початку відстань до всіх вершин дорівнює нескінченість, крім початкової вершини, до якої відстань дорівнює 0.

Потім перебираємо всі вершини, до яких відстань дорівнює 0, перебираємо суміжні з ними вершини і для них записуємо відстань рівну 1. Потім перебираємо всі вершини, до яких відстань дорівнює 1, перебираємо їх сусідів, записуємо для них відстань, рівну 2 (якщо вона до цього була рівна -1). Потім перебираємо вершини, до яких відстань була рівна 2 і тим самим визначаємо вершини, до яких відстань дорівнює 3 і т. д. Цей цикл можна повторювати або поки виявляються нові вершини на черговому кроці, або n-1 раз (де n - число вершин в графі), так як довжина найкоротшого шляху в графі не може перевершувати n-1. 

процедура BFS (s: ціле число);

почати

для i: = 1 до n do d [i]: = нескінченність;

d [s]: = 0;

для k: = 1 до n-1 робити

 для i: = 1 до n зробити

  для j: = 1 до n зробити

    якщо (d [i] = k) і [a, i] = 1) і [d] [d] [i] +1)

      тоді d [j]: = d [i] +1

кінець;