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

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

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

 

У чергу будуть закладатися вершини після того, як до них буде визначено найкоротшу відстань.

 

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

 

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

 

Запишемо алгоритм пошуку в ширину на мові Pascal

 

v  ar Q, D: масив [1..1001] longint;

a: масив [1..1000, 1..1000] longint;

i, j, n, s, f, голова, хвіст, u, v: longint;

процедура Push (x: longint);

 почати

Q [хвіст]: = x;

хвіст: = хвіст + 1

 кінець; 

функція поп;

 почати

поп: = Q [голова];

голова: = голова + 1

 кінець; 

Почніть

{зчитуємо вихідні дані: кількість вершин графа, матрицю суміжності, номери стартової і кінцевої вершини}

читати (n);

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

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

     читати (a [i, j]);

читати (s, f);

{заповнюємо масив довжин D}

для i: = 1 до n робити D [i]: = -1;

{відстань від старту до старту дорівнює нулю}

D [s]: = 0;

{кладемо стартову вершину в чергу. У черзі Q індекс head - номер першого елемента черги, tail - номер комірки після останнього елемента}

голова: 1;

хвіст: 1; 

Натиснути (ы);

{Поки черга не порожня, тобто, там є хоча б один елемент, тобто head і tail відрізняються хоча б на 1}

а голова <хвоста роблять

 почати

  u: = pop; // забираємо першу вершину з черги

{перебираємо всі вершини графа}

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

  {якщо знайшли сусіда, до якого відстань ще не обчислено}

  якщо (a [u, v] = 1) і [d [v] = -1)

   потім починай

           {обчислюємо його і кладемо цього сусіда в чергу}

           d [v]: = d [u] + 1;

           Push (v)

           кінець;

кінець;

написати (d [f]);

кінець