Урок 11                                                                                      Інформатика 11 (АП)

Лабораторна робота № 3

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

Мета.  

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

Розвиваюча. Розвивати логічне та алгоритмічне мислення, вміння застосовувати набуті знання.

Виховна. Виховувати наполегливість, самостійність, культуру оформлення

План

• Актуалізація опорних знань.
• ТБ.
• Практична робота.
• Приклади.
• Підсумки  уроку.
• Домашнє завдання.

Хід уроку

1. Організація класу.

2. Актуалізація опорних знань.

3. Інструктаж БЖД.

Інструктаж з ТБ при роботі з ПК та в комп’ютерному класі.

4. Лабораторна робота № 3 «Пошук у ширину та глибину».

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

1.     Вибираємо вершину v0 початкового графа. Надаємо значень: L(v0) = 0; V T = {v0}; l = 0.

2.     Вибираємо вершину vl з множини V T, при якій L(vl) = l.

3.     Вибираємо вершину v з різниці множин V \ V T, що суміжна (тобто сполучена ребром) з vl долучаємо:

o        вершину v до множини V T;

o        ребро (vl; v) до множини E T

і надаємо значення: L(v) = l + 1.

4.     Крок 3 здійснюємо доти, поки не буде розглянуто всі вершини з V \ V T, що постійно змінюється.

5.     Кроки 2–4 здійснюємо доти, поки не переберемо всі вершни vl з множини V T, при яких L(vl) = l.

6.     Збільшуємо величину l на 1.

7.     Кроки 2–6 здійснюємо до споравдження рівності V = V T.

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

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

1.     Усі вершини графа мітимо як "нова".

2.     Вибираємо вершину v0 початкового графа, яка буде коренем дерева. Замінюємо її мітку на "використана". Надаємо значення: v = v0.

3.     Якщо є вершини w, що суміжні (сполучені ребром) з вершиною v і мають мітку "нова", виконаємо такі дії:

o        вибираємо одну з такик вершин w і замінюємо її мітку на "використана";

o        надаємо значення v = w і знову починаємо виконання пункту 3.

4.     Якщо вершина v відмінна від v0, замінюємо поточну величину v на її безпосереднього предка і повторюємо виконання кроку 3.

Зауваження 1. Для перебору всіх можливих дерев за допомогою викладених методів на кроці 3 обох алгоритмів маємо передбачити перебір усіх можливих множин вершин і відповідних ребер, які можливо долучити на цьому кроці.

Виконання роботи.

Завдання

1.Подати дані про графа у вигляді матриці суміжностей. Які це графи?

2.   І в. Пошук шляху  у глибину(ширину) по графі з вершини А до Р

     ІІ в. Пошук шляху  у глибину(ширину) по графі з вершини 1 до 5

4. Підсумки уроку.

5. Домашнє завдання.

Повторити “Основні поняття теорії графів. Представлення графів. Пошук у ширину та глибину”.