Обхід графів (пошук на графах)

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

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

При вирішенні багатьох завдань, які використовують графи, необхідні ефективні методи регулярного обходу вершин і ребер графів. До стандартних і найбільш поширених методів відносяться:

· Пошук в глибину (Depth First Search, DFS);

· Пошук в ширину (Breadth First Search, BFS).

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

Пошук в глибину.

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

Таким чином, основна ідея пошуку в глибину - коли можливі шляхи по ребрах, що виходять з вершин, розгалужуються, потрібно спочатку повністю дослідити одну гілку і тільки потім переходити до інших гілках (якщо вони залишаться нерозглянутими).

Алгоритм пошуку в глибину.

Крок 1. Усім вершинам графа присвоюється значення “не відвідана”. Вибирається перша вершина і позначається як “відвідана”.

Крок 2. Для останньої вершини з позначкою “відвідана” вибирається суміжна вершина, що є першою вершиною з позначкою “не відвідана”. Для обранної вершини присвоюється значення “відвідана”. Якщо таких вершин немає, то береться попередня позначена вершина.

Крок 3. Повторювати Крок 2 доки всі вершини не будуть позначені як відвідані.

Приклад.

обхід графів (пошук на графах) - student2.ru

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

Тимчасова складність залежить від подання графа. Якщо застосована матриця суміжності, то тимчасова складність дорівнює O(n²), а якщо нематрічное подання - O(n + m): розглядаються всі вершини і всі ребра.

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

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

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

Алгоритм пошуку в ширину.

Крок 1. Усім вершинам графа присвоюється значення “не відвідана”. Вибирається перша вершина і позначається як “відвідана” (та заноситься у чергу).

Крок 2. Відвідується перша вершина з черги (якщо вона не позначена як “відвідана”). Всі її сусідні вершини заносяться у чергу. Після цього вона видаляється з черги.

Крок 3. Повторюється крок 2 доки черга не порожня.

Приклад.

обхід графів (пошук на графах) - student2.ru

Складність пошуку в ширину при нематрічном поданні графа дорівнює O(n + m), бо розглядаються всі n вершин і m ребер. Використання матриці суміжності призводить до оцінки O(n²).

Завдання для виконання лабораторної роботи №8.

Кожне завдання необхідно вирішити відповідно до вивчених алгоритмів обходу графа.

1. Реалізуйте програму, в якій виконується алгоритм обходу графа на основі пошуку в глибину. Для усіх вершин з непарним індексом визначити значення -1.

2. Реалізуйте програму, в якій виконується алгоритм обходу графа на основі пошуку в ширину. Для усіх вершин з парним індексом визначити значення 0.

3. Реалізуйте програму, в якій виконується алгоритм обходу графа на основі пошуку в ширину.

Використовуйте обхід графа в ширину для визначення усіх вершин графа, що знаходяться на фіксованій відстані d від даної вершини.

4. Реалізуйте програму, в якій виконується алгоритм обходу графа на основі пошуку в глибину. Використовуйте обхід графа в глибину для визначення усіх вершин графа, що знаходяться на фіксованій відстані d від даної вершини.

5. Реалізуйте програму, що перенумерує вершини графа в порядку обходу в глибину.

6. Реалізуйте програму, що перенумерує вершини графа в порядку обходу в ширину.

7. Реалізуйте програму, що виводить номери вершин доступні з вершини № 1 при обході графа в глибину.

8. Реалізуйте програму, що виводить номери вершин доступні з вершини № 1 при обході графа в ширину.

9. Реалізуйте програму, що виводить номери вершин, які мають обратні ребра при обході графа в глибину.

10. Реалізуйте програму, що виводить номери вершин, які мають обратні ребра при обході графа в ширину.

Вимоги до звіту:

Звіт з лабораторної роботи повинен відповідати наступній структурі:

1. Словесна постановка задачі. У цьому підрозділі проводиться повний опис завдання. Описується суть завдання, аналіз вхідних в неї фізичних величин, район їх допустимих значень, одиниці їх вимірювання, можливі обмеження, аналіз умов при яких завдання має рішення (не має рішення), аналіз очікуваних результатів.

2. Математична модель. У цьому підрозділі вводяться математичні описи фізичних величин і математичний опис їх взаємодій. Мета підрозділу - представити вирішувану задачу в математичній формулюванні.

3. Алгоритм рішення задачі. У підрозділі описується розробка структури алгоритму, обгрунтовується абстракція даних, завдання розбивається на підзадачі. Приводится схема алгоритму або псевдокод. Вказується оцінка алгоритму.

4. Лістинг програми.

5. Контрольний тест. Підрозділ містить набори вихідних даних і отримані в ході виконання програми результати.

6. Висновки з лабораторної роботи.

Рекомендована література:

1. Т.Кормен, Ч.Лейзерсон, Р.Ривест Алгоритмы: построение и анализ / Пер. С англ. Под ред. А.Шеня. - М.: МЦНМО, 2002. - 960 с.: 263 ил.

2. Гудман С. Хидетниеми С. Введение в разработку и анализ алгоритмов. - М.: Мир,1981.368с.

3. Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. : пер. с англ. : Уч. пос. - М. : Издательский дом «Вильямс», 2000. - 384 с. : ил. - Парал. тит. Англ.

4. Конкретная математика. Математические основы информатики 2-е издание Рональд Л. Грэхем, Дональд Э. Кнут, Орен Паташник. 784 стр., с ил.; 2012, 1 кв.; Вильямс.

5. Кнут Д. Искуство программирования. Том 1. Пер с англ. – «Вильямс», 2001. - 756 с.

6. Кнут Д. Искуство программирования. Том 2. Пер с англ. – «Вильямс», 2001. - 676 с.

7. Кнут Д. Искуство программирования. Том 3. Пер с англ. – «Вильямс», 2001. - 616 с.

Учбове видання

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторних робіт

з дисципліни «Теорія алгоритмів»

(для студентів спеціальностей напрямків «Інформатика» та «Прикладна математика»)

частина перша

Укладач:

Валерій Андрійович ВОЙТІКОВ

Редактор