Алгоритми обходу в глибину та за рівнями
Працюючи з графами часто доводиться виконувати деяку дію по одному з кожної з вершин графа. Наприклад, деяку порцію інформації слід передати кожному з комп'ютерів у мережі. При цьому ми не хочемо відвідувати якийсь комп'ютер двічі. Аналогічна ситуація виникає, якщо хочемо зібрати інформацію, а чи не поширити її. Подібний обхід можна здійснювати двома різними способами. При обході в глибину прохід вибраним шляхом здійснюється настільки глибоко, наскільки це можливо, а при обході за рівнями ми рівномірно рухаємося вздовж усіх можливих напрямків. Вивчимо тепер ці два способи докладніше. В обох випадках ми вибираємо одну з вершин графа як відправну точку. Нижче під "відвідуванням вузла" ми розуміємо виконання дії, яку необхідно здійснити у кожній вершині. Якщо, наприклад, йде пошук, то фраза про те, що ми відвідали цей вузол, означає, що ми перевірили його наявність необхідної інформації. Методи, що описуються, працюють без будь-яких змін як на орієнтованих, так і на неорієнтованих графах. Ми ілюструватимемо їх на неорієнтованих графах. За допомогою будь-якого з цих методів можна перевірити, чи зв'язаний граф, що розглядається. При обході графа можна скласти список пройдених вузлів, а після завершення обходу складений список можна порівняти зі списком всіх вузлів графа. Якщо списки містять одні й самі елементи, то граф зв'язаний. В іншому випадку у графі є вершини, до яких не можна дійти з початкової вершини, тому він незв'язний.
Обхід у глибину При обході в глибину ми відвідуємо перший вузол, а потім йдемо вздовж ребер графа, поки не впираємося в глухий кут. Вузол неорієнтованого графа є глухим кутом, якщо ми вже відвідали всі вузли, що примикають до нього. В орієнтованому графі глухим кутомтакож виявляється вузол, з якого немає ребер, що виходять. Після потрапляння в глухий кут ми повертаємося назад вздовж пройденого шляху поки не виявимо вершину, яка має ще не відвіданий сусід, а потім рухаємося в цьому новому напрямку. Процес виявляється завершеним, коли ми повернулися у відправну точку, а всі вершини, що примикають до неї, вже виявилися відвіданими. Ілюструючи цей та інші алгоритми обходу, при виборі однієї з двох вершин ми завжди вибиратимемо вершину з меншою (у числовому або лексикографічному порядку) міткою. При реалізації алгоритму вибір визначатиметься способом зберігання ребер графа. Розглянемо граф із рис. 1. Почавши обхід у глибину у вершині 1, потім відвідаємо послідовно вершини 2, 3, 4, 7, 5 і 6 і упремося в глухий кут. Потім нам доведеться повернутися до вершини 7 і виявити, що вершина 8 залишилася невідвіданою. Однак, перейшовши в цю вершину, ми негайно знову опиняємося в безвиході. Повернувшись у вершину 4, ми виявляємо, що невідвіданою залишилася вершина 9; її відвідування знову заводить нас у глухий кут. Ми знову повертаємось назад у вихідну вершину, і оскільки всі сусідні з нею вершини виявилися відвіданими, обхід закінчено.
Аналіз алгоритмів обходу При розробці алгоритмів обходи ми прагнули відвідувати кожну вершину зв'язкового графа точно один раз. Подивимося спочатку, чи нам цього вдалося досягти. При обході за рівнями мипочинали з вихідної вершини і йшли по всіх доступних ребрах, якщо вершина на другому кінці ребра не виявлялася вже відвіданою. Чи призводить це до якихось труднощів? Кожен з вузлів, в який можна потрапити з цього, виявиться відвіданим - але вздовж прямого шляху. Повернувшись до графа на рис. 1, ми помічаємо, що ми не поверталися до вузла 8 після відвідування вузлів 2 і 3. Однак усі вузли, до яких можна дістатися з вершини 8, виявляються відвіданими, оскільки ми дійшли до цієї вершини на більш ранньому проході. З іншого боку, може й у зв'язному графі опинитися вузол, якого ми не дійшли? Оскільки при кожному проході ми робимо один крок від вершин, відвіданих на попередньому проході, вузол може бути невідвіданим тільки, якщо він не є сусідом жодного з відвіданих вузлів. Але це означало б, що граф незв'язний, що суперечить нашому припущенню; отже, ми відвідаємо всі вузли. Аналогічне міркування справедливе й у обходу в глибину. У цьому випадку ми заходимо вглиб графа, поки не натрапимо на глухий кут. Чи відвідаємо ми, повертаючись, усі інші вузли? Чи може так вийти, що в якусь із вершин графа ми не зайдемо? При кожному попаданні в глухий кут ми повертаємося до першого вузла, з якого є прохід до ще не відвіданого вузла. Тоді ми прямуємо цим проходом і знову йдемо по графу в глибину. Зустрівши новий глухий кут, ми знову повертаємося назад, поки не натрапимо на першу вершину з ще не відвіданим сусідом. Щоб одна з вершин графа залишилася невідвіданою, потрібно, щоб вона не була сусідньою для жодної з відвіданих вершин. А це і означає, що граф нез'єднаний всупереч нашим припущенням. При обході вглиб ми також повинні відвідати всі вузли. Що можна сказати про ефективність такого алгоритму? Припускатимемо, що основна частина всієї роботипосідає відвідування вузла. Тоді витрати на перевірку того, чи ми вже відвідували даний вузол, і на перехід по ребру можна не враховувати. Тому порядок складності алгоритму визначається кількістю відвідувань вузлів. Як ми вже говорили, кожна вершина відвідується точно один раз, тому на графі з N вершинами відбувається N відвідувань. Таким чином, складність алгоритму дорівнює O(N).