и з декількох початкових вершин.
Як и в процессе виконан поиска завширшки, вершини графа фарбуються в Різні кольори, что свідчать про їх стан. Кожна вершина спочатку біла, потім при відкрітті в процессе поиска вона зафарбовується в сірий колір, и после Закінчення, коли ее список суміжності Повністю проскановано, вон становится чорною. Така методика гарантує, что Кожна вершина Кінець кінцем находится только в одному дереві пошуку в глибино, так что дерева не перетінаються.
Поиск в глибино такоже проставляє у вершинах Мітки годині (timestamp). Кожна вершина має две Такі Мітки - Першу d [v], у Якій вказується, коли вершина v відкрівається (і зафарбовується в сірий колір), и одного - f [v], яка фіксує момент, коли поиск завершує сканування списку суміжності вершини v и вона становится чорною. ЦІ Мітки Використовують багатьма алгоритмами и Корисні при розгляді поведінкі пошуку в глибино.
Наведено нижчих процедура DFS запісує в полі d [u момент, коли вершина u відкрівається, а в полі f [u] - момент завершення роботи з вершиною u. ЦІ Мітки годині є цілімі числами в діапазоні від 1 до 2 | V |, оскількі для кожної з | V | вершин є только один Подія Відкриття и ОДНЕ - завершення. Для кожної вершини u віконується співвідношення:
До моменту годині d [u] вершина має колір WHITE, между d [u] и f [u] - колір GRAY, а потім f [u] - колір BLACK.
Далі уявлень псевдокод алгоритмом пошуку в глибино. Вхідній граф G может буті як орієнтованім, так и неорієнтованім. Змінна time - глобальна и вікорістовується нами для міток годині.
Процедура DFS працює таким чином. У рядках 1-3 усіх вершини забарвлюються в білий колір, а їх поля? ініціалізуваліся значень nil. У рядку 4 віконується скидання глобального лічильника годині. У рядках 5-7 по черзі перевіряються усі вершини з V, и коли віявляється біла вершина, вона оброблюється помощью процедури DFS_VISIT. Шкірного разу при виклику процедури DFS_Visit (u) в рядку 7, вершина u становится коренем нового дерева лісу пошуку в глибино. При поверненні з процедури DFS Кожній вершіні u зіставляються два моменти годині - година Відкриття (discovery time) d [u] і Час Завершення (finishing time) f [u].
При шкірному виклику DFS_visit (u) вершина u спочатку має білий колір. У рядку 1 вона забарвлюється в сірий колір, в рядку 2 збільшується глобальна змінна time, а в рядку 3 віконується запису нового значення змінній time в полі годині Відкриття d [u]. У рядках 4-7 досліджуються усі вершини, суміжні з u, и віконується Рекурсивними відвідування білих вершин. При розгляданні в рядку 4 вершини v, суміжною з u, ми говоримо, что ребрпро (u, v) досліджується (explored) поиск в глибино. І Нарешті, после того, як будут досліджені усі ребра, что покідають u, в рядках 8-9 вершина и забарвлюється в чорний колір, а в полі f [u] запісується годину Завершення роботи з нею.
Зауважімо, что результат пошуку в глибино может залежаться від порядку, в якому віконується РОЗГЛЯД вершин у рядку 5 процедур DFS, а такоже від порядку відвідування суміжніх вершин у рядку 4 процедури DFS_visit. На практике це зазвічай НЕ віклікає якіх-небудь проблем, оскількі зазвічай Ефективний використанн может буті будь-який результат пошуку в глибино, прізводячі по суті до Однаково результатів роботи алгоритму, что спірається на поиск в глибино.
Чому дорівнює годину роботи процедури DFS? Циклі в рядках 1-3 и 5-7 процедури DFS віконуються за годину? (V), віключаючі годину, необхідній для виклику процедури DFS_visit. Процедура DFS_visit віклікається Рівно по одному разу для кожної вершини, оскількі вон віклікається только для білих вершин, и перше, что вона Робить, - це забарвлює надіс як параметр вершину в сірий колір. У процессе виконан DFS_Visit (v) цикл в рядках 4-7 віконується разів. Оскількі, загальна ВАРТІСТЬ виконан рядків 4-7 процедур DFS_VlSlT рівна? (Е). Година роботи процедури DFS, таким чином, Рівний? (V + Е).
. 3 Побудова мінімального остов дерева. Алгоритм Прима
Алгоритм побудова мінімального остов дерева пріпускає з єднання усіх вузлів мережі помощью Шляхів найменшої довжина. Типових завдань, для решение якої необхідній такий алгоритм, є создания (проектування) мережі доріг Із твердимо покриття, что з єднують Населені Пункти сільської місцевості, де дороги, что з'єднують дві яких-небудь Пункти могут проходити через Інші Населені пункти. Найбільш економічний проект дорожньої системи повинностей мінімізуваті Загальну Довжину доріг Із твердимо Покриття, при цьом Бажанов результат можна здобудуть путем! Застосування алгоритму побудова мінімального остов дерева.
Опішемо процедуру виконан цього алгоритму. Позначімо через N={1,2, ..., n} множини вузлів мережі и введемо Нові Позначення: - множини вузлів мережі, з'єднаних алгоритмом после виконан k-й ітерації цього алгоритму,
