шуку в глибину через рекурсію полягає в тому, що зникає необхідність явної реалізації стека.
Алгоритм пошуку описується таким чином: для кожної не проторений вершини необхідно знайти все не пройдені суміжні вершини і повторити пошук для них.
Нехай заданий граф G=(V, E), де V - безліч вершин графа, E - множина ребер графа. Припустимо, що в початковий момент часу всі вершини графа пофарбовані в білий колір. Виконаємо наступні дії:
. З безлічі всіх білих вершин виберемо будь-яку вершину, позначимо її v1.
. Виконуємо для неї процедуру DFS (v1).
. Перефарбовувати її в чорний колір.
. Повторюємо кроки 1-3 до тих пір, поки безліч білих вершин не порожньо.
Процедура DFS (параметр - вершина uU)
. Перефарбовувати вершину u в сірий колір.
. Для всякої вершини w, суміжній з вершиною u, виконуємо наступні два кроки :. Якщо вершина пофарбована в білий колір, виконуємо процедуру DFS (w) .. Офарблюємо w в чорний колір.
2.12 Алгоритм Форда-Фалкерсона
Алгоритм Форда-Фалкерсона вирішує задачу знаходження максимального потоку в транспортній мережі.
У ньому реберно-зважений граф розглядається як мережа труб, причому вага ребра (i, j) задає пропускну спроможність труби. Цей алгоритм більше підходить для завдань пов'язаних з розрахунком навантаження на локальну мережу або завдань масового обслуговування.
2.13 Алгоритм Прима
Алгоритм Прима вирішує завдання пошуку остовного дерева.
Остовним деревом графа G (V, E) називається підмножина ребер з E, що утворить дерево і з'єднує всі вершини з V. Для реберно-зважених графів особливий інтерес представляє остовное дерево мінімальної ваги, тобто остовное дерево, сума ваг ребер якого мінімальна.
остовного дерева мінімальної ваги вирішують завдання по з'єднанню безлічі точок (представляють міста, перехрестя чи що-небудь інше) мінімальною кількістю дорожнього полотна, кабелю або труб. Будь-яке дерево - це зв'язний граф з мінімальним числом ребер, а кістяк мінімальної ваги - це зв'язний граф з мінімальним реберним вагою.
Головним недоліком цього алгоритму є те, що він не дає сам маршрут, але на його основі будується алгоритм Дейкстри.
2.14 Алгоритм Дейкстри
Для пошуку найкоротшого шляху в реберно-зважених графах або графах з зваженими вершинами переважно використовувати алгоритм Дейкстри.
Для заданої вершини s він знаходить найкоротший шлях від s до всіх інших вершин, включаючи бажану вершину t.
Основна ідея вельми схожа з алгоритмом Прима. На кожній ітерації ми збираємося додавати рівно одну вершину до дерева вершин, для яких ми знаємо найкоротший шлях до s. Точно так само як і в алгоритмі Прима, ми будемо відстежувати для всіх вершин кращий шлях, відомий на даний момент, і додавати їх в порядку збільшення вартості.
Різниця між алгоритмами Прима і Дейкстри в тому, як вони оцінюють бажаність кожної вершини, що не входить в дерево. У задачі знаходження мінімального остовного дерева все, що нас цікавить, - це вага наступного потенційного ребра дерева. Для знаходження найкоротшого шляху нам потрібно вибрати вершину, найближчу (в сенсі найменшого колійного відстані) до початку. Отримуємо функцію від ваги нового ребра і від відстані від початку суміжній вершини дерева.
Якби транспортна мережа обмежувалася одним графом, то алгоритм Дейкстри був би одним з кращих виборів для пошуку оптимального шляху. Але, сама ідея алгоритму при обліку кількості пересадок може призвести до того, що деякі потенційно досяжні вершини ніколи не будуть досягнуті, тому алгоритм «витратить» всі допустимі пересадки, прагнучи зробити шлях максимально дешевим. У першу чергу це пов'язано з тим, що пошук здійснюється не тільки для цільової вершини, але і для всіх вершин входять до транспортну мережу.
2.15 Алгоритм Беллмана-Форда
Алгоритм Беллмана-Форда - алгоритм пошуку найкоротшого шляху в зваженому графі. На відміну від алгоритму Дейкстри, алгоритм Беллмана-Форда допускає ребра з негативним вагою. Запропоновано незалежно Річардом Беллманом і Лестером Фордом.
Для реалізації цього алгоритму найчастіше використовуються принципи динамічного програмування.
Він має незаперечну перевагу перед алгоритмом Дейкстри т.к. дозволяє обмежувати пошук не тільки вартістю шляху, але і кількістю ребер входять в цей шлях.
Але він не дозволяє формалізувати і алгоритмизировать обмеження на кількість пересадок, тому в ньому, як і в алгоритмі Дейкстри шлях шукається не тільки до заданої вершини, але і для всіх інших.
Основні недоліки цього алгоритму для вирішення поставленого завдання аналогічні недоліків алгоритму Дейкстри. Крім того, цей алгоритм більш ...
