Embedded Files
У процесі опрацювання графів часто доводиться виконувати обхід усіх його вершин. Існують декілька алгоритмів перегляду вершин графу, розглянемо два з них: алгоритми пошуку у глибину та пошуку в ширину.
Алгоритм пошуку в глибину. Для реалізації алгоритму пошуку в глибину використовують дві структури даних: стек для запам’ятовування ще не опрацьованих вершин і список для запам’ятовування вже опрацьованих вершин. Розглянемо сутність алгоритму пошуку в глибину.
Наведемо пояснення до цього алгоритму
Якщо стартовою є вершина V, то вибираємо вершину U, що суміжна з вершиною V. На наступному кроці для вершини U вибираємо суміжну з нею вершину. Якщо на черговому кроці розглядається вершина Q і немає вершин, суміжних із нею, і таких, що не переглядалися раніше, то повертаємося з вершини Q до тієї вершини, з якої потрапили у вершину Q і т. д. Якщо це вершина, з якої починався перегляд, тобто вершина V, і непеглянутих суміжних з нею вершин немає, то процес перегляду завершений.
Розглянемо порядок перегляду вершин графу в глибину на прикладі 1 неорієнтованого незваженого графу.
Приклад 1. Перегляд вершин можна розпочати з будь-якої вершини, наприклад із вершини 3. Із неї можна рухатися і у вершину 2, і у вершину 7.
Потім перейдемо до вершини 2, з якої рухаємося до вершини 1. Але у вершини 1 відсутня суміжна для неї вершина, яка ще не розглядалася.
Повертаємося у вершину 2 і рухаємося до вершини 4. У вершини 4 також відсутні суміжні вершини, які ще не розглядалися. Повертаємося ще раз у вершину 2 і рухаємося у вершину 5. З неї рухаємося у вершину 6, потім у вершину 7.
Для реалізації алгоритму пошуку мовою Python нумерацію вершин графу доцільно починати з 0. Суміжні вершини графу можна подавати списками (приклад 2).
Приклад 2. Список [[1, 2], [0, 2], [0, 1]] вказує, що вершина 0 має зв’язок із вершинами 1 і 2, вершина 1 — з вершинами 0 і 2, а вершина 2 — з вершинами 0 і 1.
Приклад 3. Нехай дано граф із шістьма вершинами, які мають між собою такі зв’язки: [[4, 5], [5], [3, 4], [2, 4], [0, 2, 3], [0, 1]]. Програму обходу вершин графу в глибину, починаючи з нульової вершини, зображено на рис. 8.17.
рис.8.17
Результат виконання програми:
Алгоритм пошуку в ширину. Спочатку опрацьовуються всі вершини, суміжні з поточною, а потім — «нащадки». Замість стека для збереження ще не опрацьованих вершин використовується черга. Сутність алгоритму пошуку в ширину така.
Наприклад, якщо стартовою є вершина А0, то опрацьовуються всі суміжні з нею вершини А1, А2, ..., АK, далі — суміжні вершини для кожної із вершин А1, А2, ..., АK і т. д. Будуть перебрані всі вершини, і пошук завершиться.
Розглянемо процес пошуку в ширину на прикладі графу. Порядок обходу вершин із вершини 3: з вершини 3 переглядаються вершини 2 і 7; з вершини 2 — вершини 1, 4, 5, 6, а з вершини 7 — вершина 6.
Приклад 4. Нехай дано граф із шістьма вершинами, які мають такі зв’язки між собою: [[1, 3], [0, 3, 4, 5], [4, 5], [0, 1, 5], [1, 2], [1, 2, 3]]. На рис.8.18 зображено програму обходу вершин графу в ширину, починаючи з нульової вершини.
!!! Код програми міситить помилки, які потрібно виправити !!! (рис.8.18)
Результат виконання прикладу 4 після виправлення матиме вигляд:
Завдання для самостійного виконання
Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Завдання 1. Модифікуйте програму (рис. 8.17) так, щоб обхід починався з вершини 3.
Завдання 2. Модифікуйте програму, зображену на рис. 8.18, так, щоб обхід починався з вершини 2. Виконайте програму і доведіть правильність отриманих результатів.
Завдання 3. Виконайте програму, зображену на рис. 8.18, для нового списку суміжних вершин, розробленого самостійно. Доведіть правильність отриманих результатів.
Page updated
Google Sites
Report abuse