НОУ ІНТУІТ, Лекція, Алгоритми на графах
Пошук у глибину
При пошуку в глибину відвідується перша вершина, потім необхідно йти вздовж ребер графа, до попадання в глухий кут. Вершина графа єтупиком, якщо всі суміжні з нею вершини вже відвідані. Після попадання в глухий кут потрібно повертатися назад уздовж пройденого шляху, поки не буде виявлена вершина, у якої є ще не відвідана вершина, а потім необхідно рухатися в цьому новому напрямку. Процес виявляється завершеним при поверненні до початкової вершини, причому всі суміжні з нею вершини вже повинні бути відвідані.
Таким чином, основна ідея пошуку в глибину - коли можливі шляхи по ребрах, що виходять з вершин, розгалужуються, потрібно спочатку повністю дослідити одну гілку і потім переходити до інших гілок (якщо вони залишаться нерозглянутими).
Алгоритм пошуку в глибину
Крок 1. Всім вершинам графа надається значення не відвідана. Вибирається перша вершина та позначається як відвідана.
Крок 2. Для останньої поміченої як відвідана вершини вибирається суміжна вершина, яка є першою поміченою як не відвідана, і їй присвоюється відвідана значення. Якщо таких вершин немає, то береться попередня позначена вершина.
Крок 3. Повторити крок 2 до тих пір, поки всі вершини не будуть позначені як відвідані (рис. 44.5).
Тимчасова складність залежить від уявлення графа. Якщо застосована матриця суміжності , то тимчасова складність дорівнює O(n 2 ) , і якщо нематричне уявлення – O(n+m) : розглядаються все вершини і ребра .
Пошук завширшки
При пошуку завширшки, після відвідин першої вершини, відвідуються всі сусідні з нею вершини. Потім відвідуються всі вершини, що знаходяться на відстані двохребер від початкової. При кожному новому кроці відвідуються вершини, відстань від яких до початкової на одиницю більша за попередню. Щоб запобігти повторному відвідуванню вершин, необхідно вести список відвіданих вершин. Для зберігання тимчасових даних, необхідні роботи алгоритму, використовується черга – впорядкована послідовність елементів, у якій нові елементи додаються у кінець, а старі видаляються з початку.
Таким чином, основна ідея пошуку завширшки полягає в тому, що спочатку досліджуються всі вершини, суміжні з початковою вершиною (вершина з якої починається обхід). Ці вершини знаходяться на відстані 1 від початкової. Потім досліджуються всі вершини з відривом 2 від початкової, потім усе з відривом 3 тощо. Звернемо увагу, що для кожної вершини відразу знаходяться довжина найкоротшого маршруту від початкової вершини.
Алгоритм пошуку завширшки
Крок 1. Всім вершинам графа надається значення не відвідана. Вибирається перша вершина і позначається як відвідана (і заноситься до черги).
Крок 2. Відвідується перша вершина із черги (якщо вона не позначена як відвідана). Усі її сусідні вершини заносяться в чергу. Після цього вона видаляється із черги.
Крок 3. Повторюється крок 2 доти, доки черга не порожня (рис. 44.6).
Складність пошуку завширшки при нематричному уявленні графа дорівнює O(n+m) , бо розглядаються все n вершин і m ребер. Використання матриці суміжності призводить до оцінки O(n 2 )
Ключові терміни
Вага (довжина) ребра- це число або кілька чисел, які інтерпретуються по відношенню до ребра як довжина, пропускна здатність.
Вага вершини- це число (дійсне, ціле або раціональне), поставлене у відповідність даній вершині.
Зважений граф- це граф, кожному ребру якого поставлений у відповідність його вага.
Граф- це сукупність двох кінцевих множин: безлічі точок і безлічі ліній, що попарно з'єднують деякі з цих точок.
Вершини (вузли) графа- це безліч точок, що становлять граф.
Замкнений маршрут– це маршрут у графі, у якого початкова та кінцева вершини збігаються.
Кратні ребра- це ребра, що з'єднують одну і ту ж пару вершин.
Маршрут у графі– це кінцева послідовність суміжних вершин і ребер, що чергуються, що з'єднують ці вершини.
Матриця інцидентності- це двовимірний масив, в якому вказуються зв'язки між інцидентними елементами графа (ребро та вершина).
Матриця суміжності- це двовимірний масив, значення елементів якого характеризуються суміжністю вершин графа
Мультиграф- це граф, у якого будь-які дві вершини з'єднані більш ніж одним ребром.
Неорієнтований граф (неорграф)- це граф, у якого всі ребра неорієнтовані, тобто ребрам якого не задано напрямок.
орієнтований граф (орграф)- це граф , у якого всі ребра орієнтовані, тобто ребрам якого присвоєно напрямок.
Відкритий маршрут- це маршрут у графі, у якого початкова та кінцева вершини різні.
Петля- це ребро, що з'єднує вершину саму з собою.
Пошук у глибину- це обхід графа за можливими шляхами, коли потрібно спочатку повністю дослідити одну гілку і тільки потім переходити до інших гілок (якщо вони залишаться нерозглянутими).
Пошук завширшки– це обхід графа можливими шляхами, коли після відвідування вершини, відвідуються всесусідні з нею вершини.
Простий граф- це граф, в якому немає ні петель, ні кратних ребер.
Шлях- це відкритий ланцюг, у якого всі вершини різні.
Ребра (дуги) графа- це безліч ліній, що з'єднують вершини графа.
Зв'язковий граф- це граф, у якого для будь-якої пари вершин існує шлях, що з'єднує їх.
Суміжні вершини- це вершини, з'єднані загальним рубом.
Змішаний граф- це граф, що містить як орієнтовані, так і неорієнтовані ребра.
Список ребер- це безліч, утворене парами суміжних вершин
Тупик- це вершина графа, для якої всі суміжні з нею вершини вже відвідані
Ланцюг- це маршрут у графі, у якого всі ребра різні.
Цикл- це замкнутий ланцюг, у якого різні всі його вершини, за винятком кінцевих.