Інформатика – Поглиблений рівень

Прочитайте!

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

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

Використовуючи алгоритм виконаємо пошук у ширину:

Наведемо пояснення до цього алгоритму

Якщо стартовою є вершина 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]]. Програму обходу вершин графу в глибину, починаючи з нульової вершини.

Результат виконання програми:

Алгоритм пошуку в ширину. Спочатку опрацьовуються всі вершини, суміжні з поточною, а потім — «нащадки». Замість стека для збереження ще не опрацьованих вершин використовується черга. Черга (одностороння черга) — лінійний список, у якому всі операції вставки здійснюються на одному з кінців списку, а всі операції знищення — на іншому (останній прийшов – останній пішов).

Сутність алгоритму пошуку в ширину така.

Використовуючи алгоритм виконаємо пошук у ширину:

Наведемо пояснення до цього алгоритму.

Наприклад, якщо стартовою є вершина А0, то опрацьовуються всі суміжні з нею вершини А1, А2, …, АK, далі — суміжні вершини для кожної із вершин А1, А2, …, АK і т. д. Будуть перебрані всі вершини, і пошук завершиться.
Розглянемо процес пошуку в ширину на прикладі графу (рис. 8.16, б). Порядок обходу вершин із вершини 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 зображено програму обходу вершин графу в ширину, починаючи з нульової вершини.

Увага!!! Код програми містить помилку, яку потрібно виправити, після виправлення помолки результат виконання програми матиме вигляд:

Завдання для самостійного виконання

Завдання 1. Модифікуйте програму, зображену на рис. 8.18, так, щоб обхід починався з вершини 2. Виконайте програму і доведіть правильність отриманих результатів.

Завдання 2. Модифікуйте програму (рис. 8.17) так, щоб обхід починався з вершини 3.

Завдання 3. Виконайте програму, зображену на рис. 8.18, для нового списку суміжних вершин, розробленого самостійно. Доведіть правильність отриманих результатів.

Пройти тестування

Завантажити завдання