Теорія графів. Пошук у глибину

У п'ятницю 11.11.11 відбулося чергове заняття ообласної чно-дистанційної школи олімпійського резерву з програмування. Тема заняття "Теорія графів. Пошук у глибину".

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

Нехай дано граф G = (V, E) і фіксована початкова вершина v. При пошуку в глибину змінюється стратегія перегляду вершин графа. Рух здійснюється від однієї вершини до іншої, з нею суміжної, поступово віддаляючись від початкової вершини, доки не дійдемо до тупика. Вершина неорієнтованого графа є тупиком, якщо вже відвідані всі суміжні з нею вершини. В орієнтованому графі ним може бути вершина, з якої не виходить жодне ребро (вихідний степінь 0).

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

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

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

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

Якщо суміжних невідвіданих вершин не знайдено, то повертаємось з рекурсії.

Задача.
Кожен кабінет інформатики в школі має власну локальну мережу. Шкільні комп’ютери мають імена, що відповідають числам від 1 до N. Для підключення всіх комп’ютерів до глобальної мережі Інтернет директор вирішив зробити об’єднану локальну мережу школи. Для цього від кожного кабінету інформатики треба протягти кабель до шкільного хаба. Скільки вільних портів повинен мати хаб для забезпечення підключення кожного кабінету?

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

Теорія графів. Пошук у ширину

У п'ятницю 4 листопада о 15.00 відбудеться чергове заняття обласної очно-дистанційної Школи олімпійського резерву з програмування.

Тема заняття "Теорія графів. Пошук у ширину".

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

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

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

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

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

Нехай дано граф G = (V, E) і фіксована початкова вершина v. При обході графа в ширину на першому кроці відвідуються всі вершини, сусідні з початковою. При другому проході відвідуються всі вершини "на відстані двох ребер" від початкової. При кожному новому проході опрацьовуються вершини, відстань від яких (кількість ребер) до початкової на одиницю більша від попередньої. У графі можуть бути цикли, тому не виключено, що одну й ту саму вершину можна досягти з початковою двома різними шляхами. Ця вершина опрацьовується один раз, коли буде досягнутою найкоротшим до неї шляхом, і відвідувати її другий раз немає сенсу. Тому, щоб попередити повторне відвідування, доцільно або вести список відвіданих вершин, або завести для кожної прапорець, який би вказував, чи опрацьована вже ця вершина.