Пошук в глибину та ширину

Опишемо метод пошуку в простому зв'язному графі, який являє собою одну з основних методик проектування алгоритмів, пов'язаних із графами. Цей метод називають пошуком углиб, або DFS-методом (від англ. depth first search).

Нехай G=(V. Е) — простий зв'язний граф, усі вершини якого позначено попарно різними символами. У процесі пошуку вглиб вершинам графа G надають номери (DFS-номери) та певним способом позначають ребра. У ході роботи алгоритму використовують структуру даних для збереження множин, яку називають стеком (англ. stack — стіг). Зі стеку можна вилучити тільки той елемент, котрий було додано до нього останнім: стек працює за принципом „останнім прийшов — першим вийшов" (last in, first out — скорочено LIFO). Інакше кажучи, додавання й вилучення елементів у стеку відбувається з одного кінця, який називають верхівкою стеку. DFS-номер вершини х позначають DFS(x).

Алгоритм пошуку вглиб у простому зв'язному графі

Крок 1. Почати з довільної вершини v_s Виконати DFS(v_s):=1. Включити цю вершину в стек.

Крок 2. Розглянути вершину у верхівці стеку: нехай це вершина х. Якщо всі ребра, інциденти вершині х, позначено, то перейти до кроку 4, інакше - до кроку 3.

Крок 3. Нехай { х, у } - непозначене ребро. Якщо DFS(y) уже визначено, то позначити ребро { х, у } штриховою лінією та перейти до кроку 2. Якщо DFS(y) не визначено, то позначити ребро { х, у } потовщеною суцільною лінією, визначити DFS(y) як черговий DFS-номер, включити цю вершину в стек і перейти до кроку 2.

Крок 4. Виключити вершину х зі стеку. Якщо стек порожній, то зупинитись, інакше — перейти до кроку 2.

Щоб вибір номерів був однозначним, доцільно домовитись, що вершини, суміжні з тією, яка вже отримала DFS-номер, аналізують за зростанням їх порядкових номерів (або в алфавітному порядку). Динаміку роботи алгоритму зручно відображати за допомогою таблиці з трьома стовпцями: вершина, DFS-номер. уміст стеку. Її називають протоколом обходу графа пошуком вглиб.

У процесі пошуку вшир вершини графа проглядають в іншій послідовності, ніж у методі пошуку вглиб, і їм надають BFS-номери (від англ. breadth first search). BFS-номер вершини х позначають BFS(х). Під час пошуку рухаються вшир, а не вглиб: спочатку проглядають усі сусідні вершини, після цього — сусіди сусідів і так далі.

У ході реалізації алгоритму використовують структуру даних для збереження множин, яку називають чергою (англ. queue). Із черги можна вилучити тільки той елемент, який перебував у ній найдовше: працює принцип „першим прийшов — першим вийшов" (first in, first out — скорочено FIFO). Елемент включається у хвіст черги, а виключається з її голови. Пошук ушир, узагалі кажучи, відрізняється від пошуку вглиб заміною стек; на чергу. Після такої модифікації що раніше відвідується вершина (включається в чергу), то раніше вона використовується (і виключається з черги). Використання вершини полягає в перегляді одразу всіх іще не відвіданих її сусідів. Усю процедуру подано нижче.

Алгоритм пошуку вшир у простому зв'язному графі

Крок 1. Почати з довільної вершини v_s. Виконати BFS(v_s):=1. Включити вершину v_s, у чергу.

Крок 2. Розглянути вершину, яка перебуває на початку черги; нехай це буде вершина х. Якщо для всіх вершин, суміжних із вершиною х, уже визначено BFS-номери, то перейти до кроку 4, інакше — до кроку 3.

Крок 3. Нехай { х, у } — ребро, у якому номер BFS(y) не визначено. Позначити це ребро потовщеною суцільною лінією, визначити BFS(y) як черговий BFS-номер, включити вершину у у чергу й перейти до кроку 2.

Крок 4. Виключити вершину х із черги. Якщо черга порожня, то зупинитись, інакше — перейти до кроку 2.

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

Дата добавления: 2014-01-07