- обхід графа В якості заключного прикладу в цьому розділі розглянемо одну з найбільш важливих рекурсивних...
- Посилання для частини II
обхід графа
В якості заключного прикладу в цьому розділі розглянемо одну з найбільш важливих рекурсивних програм: рекурсивний обхід графа, або пошук в глибину (depth -first search). Цей метод систематичного відвідування всіх вузлів графа являє собою безпосереднє узагальнення методів обходу дерев, розглянутих в розділі 5.6, і служить основою для багатьох базових алгоритмів обробки графів (див. Частину 7). Це простий рекурсивний алгоритм. Починаючи з будь-якого вузла v, ми
- відвідуємо v;
- (Рекурсивно) відвідуємо кожен (не відвідування) вузол, пов'язаний з v.
Якщо граф є зв'язковим, з часом будуть відвідані всі вузли. Програма 5.21 є реалізацією цієї рекурсивної процедури.
Програма 5.21. Пошук в глибину
Для відвідування в графі всіх вузлів, пов'язаних з вузлом до, ми помічаємо його як відвіданий, а потім (рекурсивно) відвідуємо все не відвідані вузли в списку суміжності вузла к.
void traverse (int k, void visit (int)) {visit (k); visited [k] = 1; for (link t = adj [k]; t! = 0; t = t -> next) if (! visited [t -> v]) traverse (t -> v, visit); }
Наприклад, припустимо, що використовується представлення у вигляді списків зв'язності, наведене для графа на Мал. 3.15 . на Мал. 5.32 приведена послідовність викликів, виконаних при пошуку в глибину в цьому графі, а послідовність проходження ребер графа показана в лівій частині Мал. 5.33 . При проходженні кожного з ребер графа можливі два варіанти: якщо ребро призводить до вже відвідування вузла, ми ігноруємо його; якщо воно призводить до ще не відвіданих вузлу, ми проходимо по ньому за допомогою рекурсивного виклику. Безліч всіх пройдених таким чином ребер утворює кістяк графа.
Мал.5.32.
Виклики функції пошуку в глибину
Ця послідовність викликів функцій реалізує пошук в глибину для графа, наведеного на Мал. 3.15 . Дерево, яке описує структуру рекурсивних викликів (вгорі), називається деревом пошуку в глибину.
Різниця між пошуком в глибину і загальним обходом дерева (див. Програму 5.14) полягає в тому, що необхідно явно виключити відвідування вже відвіданих вузлів. У дереві такі вузли не зустрічаються. Дійсно, якщо граф є деревом, рекурсивний пошук у глибину, що починається з кореня, еквівалентний прямому обходу.
Лемма 5.10. Час, необхідний для пошуку в глибину в графі з V вершинами і E ребрами, пропорційно V + E, якщо використовується уявлення графа у вигляді списків суміжності.
У поданні у вигляді списків суміжності кожному ребру графа відповідає один вузол в списку, а кожній вершині графа відповідає один покажчик на початок списку. Пошук в глибину використовує кожен з них не більше одного разу. 
Оскільки час, необхідний для побудови уявлення у вигляді списків суміжності з послідовності ребер (див. Програму 3.19), також пропорційно V + E, пошук в глибину забезпечує рішення задачі зв'язності з "Вступ" з лінійним часом виконання. Однак для дуже великих графів рішення виду об'єднання -пошук можуть виявитися кращим, оскільки для подання всього графа потрібен обсяг пам'яті, пропорційний E, а для рішень об'єднання -пошук - пропорційний тільки V.
Як і в разі обходу дерева, можна визначити метод обходу графа, при якому використовується явний стек (див. Мал. 5.34 ). Можна уявити собі абстрактний стек, що містить подвійні елементи: вузол і покажчик на список суміжності для цього вузла. Якщо спочатку стек містить початковий вузол, а покажчик вказує на перший елемент списку суміжності для цього вузла, алгоритм пошуку в глибину еквівалентний входу в цикл, в якому спочатку відвідується вузол з верхівки стека (якщо він ще не був відвіданий); потім зберігається вузол, вказаний поточним покажчиком списку суміжності; потім посилання зі списку суміжності зсувається на наступний вузол (з виштовхуванням елемента, якщо досягнуто кінець списку суміжності); і, нарешті, в стек заноситься елемент для збереженого вузла з посиланням на перший вузол його списку суміжності.
Мал.5.33.
Пошук в глибину і пошук в ширину
При пошуку в глибину (зліва) перебираються всі вузли, з поверненням до попереднього вузла, коли всі зв'язки даного вузла перевірені. При пошуку в ширину (праворуч) спочатку перебираються всі зв'язки даного вузла, а потім виконується перехід до наступного вузла.
Або ж, як це було зроблено для обходу дерева, можна створити стек, що містить тільки посилання на вузли. Якщо спочатку стек містить початковий вузол, ми входимо в цикл, в якому відвідуємо вузол на верхівці стека (якщо він ще не був відвіданий), потім заносимо в стек всі вузли, суміжні з цим вузлом. на Мал. 5.34 видно, що для нашого прикладу графа обидва методи еквівалентні пошуку в глибину, причому еквівалентність зберігається і в загальному випадку.
Алгоритм відвідування верхнього вузла і занесення всіх його сусідів - проста формулювання пошуку в глибину, але з Мал. 5.34 зрозуміло, що цей метод може залишати в стеці декількох копій кожного вузла. Це відбувається навіть у випадку перевірки, відвідували чи кожен вузол, який повинен бути поміщений в стек, і якщо так, то відмови від занесення в стек такого вузла. Щоб уникнути цієї проблеми можна скористатися реалізацією стека, яка усуває дублювання за допомогою правила "забути старий елемент": оскільки найближча до верхівки стека копія завжди відвідується першої, всі інші копії просто виштовхуються з стека.
Динаміка стану стека для пошуку в глибину, показана на Мал. 5.34 , Заснована на тому, що вузли кожного списку суміжності з'являються в стеці в тому ж порядку, що і в списку. Для отримання цього порядку для даного списку суміжності при занесенні вузлів по одному необхідно заштовхнути в стек спочатку останній вузол, потім передостанній і т.д.
Мал.5.34.
Динаміка стека при пошуку в глибину
Стек, що забезпечує пошук в глибину, можна уявити собі як що містить елементи, кожен з яких складається з вузла і посилання на список суміжності для цього вузла (показаний вузлом в гуртку) (ліворуч). Таким чином, обробка починається з знаходиться в стеку вузла 0 з посиланням на перший вузол в його списку суміжності - вузол 7. Кожен рядок відображає результат виштовхування з стека, занесення посилання на наступний вузол в списку відвіданих вузлів і занесення в стек елемента для не відвідування вузлів . Цей процес можна також уявити собі у вигляді простого занесення в стек всіх вузлів, суміжних з будь-яким не відвіданих вузлом (праворуч).
Більш того, щоб обмежити розмір стека числом вершин і все-таки відвідувати вузли в тому ж порядку, як і при пошуку в глибину, необхідно використовувати стек з забування старого елемента. Якщо відвідування вузлів в тому ж порядку, що і при пошуку в глибину, не має значення, обох цих ускладнень можна уникнути і безпосередньо сформулювати нерекурсивний метод обходу графа з використанням стека, який виглядає так. Після початкового занесення в стек початкового вузла ми входимо в цикл, в якому відвідуємо вузол на верхівці стека, потім обробляємо його список суміжності, поміщаючи в стек кожен вузол (якщо він ще не був відвіданий); тут повинна використовуватися реалізація стека, яка забороняє дублювання за правилом "ігнорувати новий елемент". Цей алгоритм забезпечує відвідування всіх вузлів графа аналогічно пошуку в глибину, але не є рекурсивним.
Алгоритм, описаний в попередньому абзаці, заслуговує на увагу, оскільки замість стека можна використовувати будь-який АТД узагальненої черзі і все ж відвідати кожен з вузлів графа (плюс згенерувати розгорнуте дерево). Наприклад, якщо замість стека задіяти чергу, то вийде пошук в ширину, який аналогічний обходу дерева за рівнями. Програма 5.22 - реалізація цього методу (за умови, що використовується реалізація черзі на зразок програми 4.12); приклад цього алгоритму в дії показаний на Мал. 5.35 . У частині 6 буде розглянуто безліч алгоритмів обробки графів, заснованих на більш складних АТД узагальнених черг.
І при пошуку в ширину, і при пошуку в глибину відвідуються всі вузли графа, але в абсолютно різному порядку (див. Мал. 5.36 ). Пошук в ширину подібний армії розвідників, розісланих по всій території; пошук в глибину відповідає єдиному розвіднику, який проникає якнайдалі вглиб незвіданій території, повертаючись тільки в разі, якщо наштовхується на глухий кут. Це базові методи вирішення завдань, що грають істотну роль у багатьох областях комп'ютерних наук, а не тільки в пошуку в графах.
Програма 5.22. Пошук в ширину
Щоб відвідати в графі всі вузли, пов'язані з вузлом до, вузол до поміщається в чергу FIFO, потім виконується цикл, в якому з черги вибирається наступний вузол і, якщо він ще не був відвіданий, він відвідується, а в стек заталкиваются все не відвідані вузли з його списку суміжності. Цей процес триває до тих пір, поки черга не спорожніє.
void traverse (int k, void visit (int)) {QUEUE <int> q (V * V); q.put (k); while (! q.empty ()) if (visited [k = q.get ()] == 0) {visit (k); visited [k] = 1; for (link t = adj [k]; t! = 0; t = t -> next) if (visited [t -> v] == 0) q.put (t -> v); }}
Мал. 5.35. Динаміка черзі при пошуку в ширину
Обробка починається з вузла 0 в черзі, потім ми витягаємо вузол 0, відвідуємо його і поміщаємо в чергу вузли 7 5 2 1 6 з його списку суміжності, причому саме в цьому порядку. Потім ми витягаємо вузол 7, відвідуємо його і поміщаємо в чергу вузли з його списку суміжності, і т.д. У разі заборони дублювання за правилом "ігнорувати новий елемент" (праворуч) ми отримуємо такий же результат без зайвих елементів в черзі.
Мал.5.36.
Дерева обходу графів
На цій схемі показані пошук в глибину (в центрі) і пошук в ширину (внизу), виконані наполовину в великому графі (вгорі). При пошуку в глибину обхід виконується від одного вузла до наступного, так що більшість вузлів пов'язано тільки з двома іншими.
А при пошуку в ширину відвідуються все вузли, пов'язані з даними, перш ніж рухатися далі; тому деякі вузли пов'язані з безліччю інших.
вправи
5.92. Побудувавши діаграми, відповідні Мал. 5.33 (Зліва) і 5.34 (праворуч), покажіть, як відбувається відвідування вузлів при рекурсивном пошуку в глибину в графі, побудованому для послідовності ребер 0 -2, 1 -4, 2 -5, 3 -6, 0 -4, 6 -0 і 1 -3 (див. вправу 3.70).
5.93. Побудувавши діаграми, відповідні Мал. 5.33 (Зліва) і 5.34 (праворуч), покажіть, як відбувається відвідування вузлів при пошуку в ширину (з використанням стека) в графі, побудованому для послідовності ребер 0 -2, 1 -4, 2 -5, 3 -6, 0 -4 , 6 -0 і 1 -3 (див. вправу 3.70).
5.94. Побудувавши діаграми, відповідні Мал. 5.33 (Зліва) і 5.35 (праворуч), покажіть, як відбувається відвідування вузлів при пошуку в ширину (з використанням черги) в графі, побудованому для послідовності ребер 0 -2, 1 -4, 2 -5, 3 -6, 0 -4 , 6 -0 і 1 -3 (див. вправу 3.70).
5.95. Чому час виконання, яка згадується в лемі 5.10, пропорційно V + E, а не просто E?
5.96. Побудувавши діаграми, відповідні Мал. 5.33 (Зліва) і 5.35 (праворуч), покажіть, як відбувається відвідування вузлів при пошуку в глибину (з використанням стека і правила "забути старий елемент") в графі, наведеному на Мал. 3.15 .
5.97. Побудувавши діаграми, відповідні Мал. 5.33 (Зліва) і 5.35 (праворуч), покажіть, як відбувається відвідування вузлів при пошуку в глибину (з використанням стека і правила "ігнорувати новий елемент") в графі, наведеному на Мал. 3.15 .
5.98. Реалізуйте пошук в глибину з використанням стека для графів, які представлені списками суміжності.
5.99. Реалізуйте рекурсивний пошук у глибину для графів, які представлені списками суміжності.
перспективи
Рекурсія лежить в основі ранніх теоретичних досліджень природи обчислень. Рекурсивні функції і програми грають головну роль в математичних дослідженнях, в яких робиться спроба поділу завдань на піддаються вирішенню на комп'ютері і на непридатні для цього.
В ході такого короткого розгляду просто неможливо повністю висвітлити настільки великі теми, як дерева і рекурсія. Багато найвдаліші приклади рекурсивних програм будуть постійно зустрічатися нам протягом всієї книги - до них відносяться алгоритми "розділяй і володарюй" і рекурсивні структури даних, які успішно застосовуються для вирішення широкого спектра завдань. Для багатьох додатків немає сенсу виходити за рамки простої безпосередньої рекурсивної реалізації; для інших буде розглянуто висновок нерекурсивних і висхідних реалізацій.
У цій книзі основна увага приділена практичним аспектам побудови рекурсивних програм і структур даних. Наша мета - застосування рекурсії для створення витончених і ефективних реалізацій. Для досягнення цієї мети необхідно особливо враховувати небезпеку використання простих програм, які ведуть до експоненціального збільшення кількості викликів функцій або неприпустимо великій глибині вкладеності. Незважаючи на цей недолік, рекурсивні програми і структури даних вельми привабливі, оскільки часто вони наводять на індуктивні міркування, які допомагають переконатися в правильності і ефективності розроблених програм.
У даній книзі дерева використовуються як для спрощення розуміння динамічних властивостей програм, так і в якості динамічних структур даних. У главах 12 - 15 особливо велика увага приділяється роботі з деревоподібними структурами. Властивості, описані в цьому розділі, надають базову інформацію, яка потрібна для ефективного застосування деревовидних структур.
Незважаючи на центральну роль в розробці алгоритмів, рекурсія - зовсім не панацея на всі випадки життя. Як було показано при вивченні алгоритмів обходу дерев і графів, алгоритми з використанням стека (які рекурсивно за своєю природою) - не єдина можливість при необхідності управляти відразу декількома обчислювальними завданнями. Ефективна техніка розробки алгоритмів для вирішення багатьох завдань полягає в використанні реалізацій узагальнених черг, що відрізняються від стеків; такі черги дозволяють вибирати таку задачу відповідно до яким-небудь більш суб'єктивним критерієм, ніж простий вибір самої останньої. Структури даних і алгоритми, які ефективно підтримують такі операції - основна тема "Черги з пріоритетами і пірамідальна сортування" , А з багатьма прикладами їх застосування ми зустрінемося під час вивчення алгоритмів обробки графів в частині 7.
Посилання для частини II
Існує безліч підручників для початківців, присвячених структурам даних. Наприклад, в книзі Стендіш (Standish) теми зв'язкових структур, абстракцій даних, стеків і черг, розподілу пам'яті і створення програм висвітлюються більш докладно, ніж тут. Звичайно, класичні книги Керніган і Рітчі (Kernighan -Ritchie) і Страуструпа (Stroustrup) - безцінні джерела інформації по реалізаціям на С і С ++. Книги Мейерса (Meyers) також містять корисну інформацію про реалізації на C ++.
Розробники PostScript, ймовірно, не могли навіть і припускати, що розроблений ними мову буде представляти інтерес для людей, які вивчають основні алгоритми і структури даних. Сам по собі ця мова не представляє особливої складності, а довідкове керівництво по ньому грунтовно і доступно.
Парадигма "клієнт-інтерфейс -Реалізація" докладно і з безліччю прикладів описується в книзі Хенсона (Hanson). Ця книга - чудовий довідник для тих програмістів, які мають намір писати надійний і стерпний код для великих систем.
Книги Кнута (Knuth), особливо 1-й і 3-й томи, залишаються авторитетним джерелом інформації за властивостями елементарних структур даних. Книги Баеcа -Ятеса (Baeza -Yates) і Гонне (Gonnet) містять більш свіжу інформацію, підкріплену значним бібліографічним переліком. Книга Седжвика і Флажоле (Sedgewick and Flajolet) докладно висвітлює математичні властивості дерев.
1. Adobe Systems Incorporated, PostScript Language Reference Manual, second edition, Addison -Wesley, Reading, MA, 1990..
2. R. Baeza -Yates and GH Gonnet, Handbook of Algorithms and Data Structures, second edition, Addison -Wesley, Reading, MA, 1984.
3. DR Hanson, C Interfaces and Implementations: Techniques for Creating Reusable Software, Addison -Wesley, 1997..
4. Брайан У. Керніган, Денніс М. Рітчі, Мова програмування C (Сі), 2-е видання, ВД "Вільямс", 2008 р
5. Д.Е. Кнут, Мистецтво програмування, том 1: Основні алгоритми, 3-е видання, ВД "Вільямс", 2008 р .; Д.Е. Кнут, Мистецтво програмування, том 2: Получісленние алгоритми, 3-е видання, ВД "Вільямс", 2008 р .; Д.Е. Кнут, Мистецтво програмування, том 3. Сортування і пошук, 2 -е видання, ВД "Вільямс", 2008 р
6. S. Meyers, Effective C ++, second edition, Addison -Wesley, Reading, MA, 1996..
7. S. Meyers, More Effective C ++, Addison -Wesley, Reading, MA, 1996..
8. R. Sedgewick and P Flajolet, An Introduction to the Analysis of Algorithms, Addison -Wesley, Reading, MA, 1996..
9. TA Standish, Data Structures, Algorithms, and Software Principles in C, Addison -Wesley, 1995.
10. B. Stroustrup, The C ++ Programming Language, third edition, Addison -Wesley, Reading MA, 1997..
Пропорційно V + E, а не просто E?