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

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

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

Для наочності ми будемо вважати, що в процесі роботи алгоритму вершини графа можуть бути білими, сірими та чорними. Спочатку вони всі білі, але в ході роботи алгоритму біла вершина може стати сірою, а сіра - чорною (але не навпаки). Зустрівши нову вершину, алгоритм пошуку фарбує її, так що пофарбовані (сірі або чорні) вершини - це в точності ті, які вже виявлені. Різниця між сірими і чорними вершинами використовується алгоритмом для управління порядку обходу: сірі вершини утворюють «лінію фронту», а чорні - «тил». Більш точно, підтримується така властивість: якщо (u, v) £ E та u чорна, то v - сіра або чорна вершина. Таким чином, тільки сірі вершини можуть мати суміжні невиявлені вершини.

Спочатку дерево пошуку складається тільки з кореня - початкової вершини s. Як тільки алгоритм виявляє нову білу вершину v, суміжну з раніше знайденою вершиною u, вершина v (разом з ребром (u, v)) додається до дерева пошуку, стаючи дитиною (child) вершини u та стає батьком (parent) v. Кожна вершина виявляється тільки одного разу, так що двох батьків у неї бути не може. Поняття предка (ancestor) і нащадка (descendant) визначаються як звичайно. Рухаючись від вершини до кореня, ми проходимо всіх її предків.

Наведена нижче процедура BFS (breadth-first search - пошук в ширину) використовує представлення графа G = (V, Е) списками суміжних вершин. Для кожної вершини та графа додатково зберігаються її колір color [u] та її попередник π [u]. Якщо попередника немає (наприклад, якщо u = s або не розпізнається), π [u] = NIL. Крім того, відстань від s до u записується в масив d [u]. Процедура використовує також чергу Q (FIFO) для зберігання безлічі сірих вершин.

BFS $ (G, s) $

1 for (для) всіх вершин $u \ in V [G] - \ {s \} $

2 do $ color [u] \ leftarrow $ БІЛИЙ

3 $ d [u] \ leftarrow \ infty $

4 $ \ pi [u] \ leftarrow $ MIL

5 $ color [s] \ leftarrow $ СІРИЙ

6 $ d [s] \ leftarrow 0 $

7 $ \ pi [s] \ leftarrow $ MILL

8 $ Q \ leftarrow \ {s \> $

9 while $ Q \ ne \ emptyset $

10 do $ u \ leftarrow head [Q] $

11 for (для) всіх $ v \ in Adj [u] $

12 do if $ color [v] = $ БІЛИЙ

13 then $ color [v] \ leftarrow $ СІРИЙ

14 $ d [v] \ leftarrow d [u] + l $

15 $ \ pi [v] \ leftarrow u $

16 Enqueue ($ Q, v $)

17 Dequeue ($ Q $)

18 $ color [u] \ leftarrow $ ЧОРНИЙ

На рисунку. 1. 2a. представлений приклад виконання процедури \ textsc {BFS>

Виконання процедури \ textsc {BFS} для неорієнтованого графа. Ребра формованого дерева показані сірими. Усередині кожної вершини $ і $ вказано значення $ d [u] $. Показано стан черги $ Q $ перед кожним повторенням циклу в рядках 9-18. Поруч з елементами черги показані відстані від кореня.

У рядках 1-4 всі вершини стають білими, всі значення $ d $ нескінченними, і батьком всіх вершин оголошується \ textsc {nil}. Рядки 5-8 фарбують вершину $ s $ в сірий колір і виконують пов'язані з цим дії: в рядку 6 відстань $ d [s] $ оголошується рівним $ 0 $, а в рядку $ 7 $ говориться, що батька у $ s $ немає. Нарешті, в рядку $ 8 $ вершина $ s $ поміщається в чергу $ Q $, і з цього моменту чергу буде містити всі сірі вершини і тільки їх.

Основний цикл програми (рядки 9-18) виконується, поки черга не порожня, тобто існують сірі вершини (вершини, які вже виявлені, але списки суміжності яких ще не переглянуті). У рядку 10 перша така вершина поміщається в $ і $. Цикл \ textbf {for} в рядках 11-16 переглядає всі суміжні з нею вершини. Виявивши серед них білу вершину, ми робимо сірою (рядок 13), оголошуємо $ і $ батьком (рядок 15) і встановлюємо відстань рівним $ d [u] + l $ (рядок 14 ). Нарешті, ця вершина додається у хвіст черги $ Q $ (рядок 16). Після цього вже можна видалити вершину $ і $ з черги $ Q $, перефарбувавши цю вершину в чорний колір (рядки 17-18).

Працюючи на графі $ G = (V, E) $ (орієнтованому або неорієнтованому) з початковою вершиною $ s $, процедура \ textsc {BFS} виявить (зробить чорним) всі досяжні з $ s $ вершини, і для всіх $ v \ in V $ буде виконано рівність $ d [v] = \ delta (s, v) $. Крім того, для будь-якої вершини $ v \ ne s $, досяжною з $ s $, один з найкоротших шляхів з $ s $ в $ v $ можна отримати додаванням ребра $ (\ pi [v], v) $ до найкоротшого шляху з $ s $ в $ \ pi [v] $. Для недосяжної з $ s $ вершини значення $ \ pi [s] $ дорівнює \ textsc {nil}.

⇐ Предыдущая 1 234 5 Следующая ⇒