|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[154] иск повторяется из нескольких вершин. Говоря дальше о поиске в глубину, мы всегда предполагаем, что так и делается (поиск повторяется). Мы получаем подграф предшествования (predecessor subgraph), определённый так: Gv = (V,EV), где Подграф предшествования представляет собой лес поиска в глубину (depth-first forest), состоящий из деревьев поиска в глубину (deep-first trees). Алгоритм поиска в глубину также использует цвета вершин. Каждая из вершин вначале белая. Будучи обнаруженной (discovered), она становится серой; она станет чёрной, когда будет полностью обработана, то есть когда список смежных с ней вершин будет просмотрен. Каждая вершина попадает ровно в одно дерево поиска в глубину, так что эти деревья не пересекаются. Помимо этого, поиск в глубину ставит на вершинах метки времени (timestamps). Каждая вершина имеет две метки: в d[v] записано, когда эта вершина была обнаружена (и сделана серой), а в f[v] - когда была закончена обработка списка смежных с v вершин (и v стала чёрной). Эти метки времени используются во многих алгоритмах на графах и полезны для анализа свойств поиска в глубину. В приводимой далее процедуре DFS (Depth-First Search - поиск в глубину) метки времени d[v] и f[v] являются целыми числами от 1 до 2\V\; для любой вершины и выполнено неравенство Вершина и будет белой до момента d[u], серой между d[u] и f[u] и чёрной после /[и]. Исходный граф может быть ориентированным или неориентированным. Переменная time - глобальная переменная текущего времени, используемого для пометок. DFS$(G)$ 1for (для) всех вершин $u\in V[G]$ 2\hspace{lcm} do $color[u]\leftarrow$ белый 3\hspace{2cm> $\pi[u]\leftarrow NIL$ 4$time\leftarrow 0$ 5for (для) всех вершин $u\in V[G]$ 6\hspace{lcm} do if $color[u]=$ белый 7\hspace{2cm> then DFS-Visit$(u)$ DFS-Visit(u) 1 $color[u]\leftarrow$ белый вершина $u$ была белой Еж = {(тгН, v) : v е Va,ndir[v] ф NIL} d[u] < f[u] Рис. 23.3 23.4 Исполнение алгоритма DFS для ориентированного графа. После просмотра каждое ребро становится либо серым (если оно включается в дерево поиска) или пунктирным (обратные рёбра помечены буквой В (back), перекрёстные - буквой С (cross), прямые - буквой F (forward)). У каждой вершины показаны времена начала и конца обработки. 2$d[u]\leftarrow time\leftarrow time+l$ 3\textsc{for} (для) всех $v\in Adj[u]$ обработать ребро $(u,v)$ 4\hspace{lcm} \textsc{do if} $color[v]=$ белый 5\hspace{2cm} \textsc{then} $\pi[v]\leftarrow u$ 6\hspace{3cm} DFS-Visit$(v)$ 7$color[u]\leftarrow$ ч\"~~а5рный вершина обработана, делаем е\"~~а5 чер! 8$f[u]\leftarrow time\leftarrow time+l$ На рис. 23.4 показана работа процедуры DFS на графе рис. 23.2. В строках 1-3 все вершины красятся в белый цвет; в поле 7г помещается nil. В строке 4 уставливается начальное (нулевое) время. В строках 5-7 вызывается процедура DFS-Visit для всех вершин (которые остались белыми к моменту вызова - предыдущие вызовы процедуры могли сделать их чёрными). Эти вершины становятся корнями деревьев поиска в глубину. В момент вызова DFS-Visit(m) вершина и - белая. В строке 1 она становится серой. В строке 2 время её обнаружения заносится в d[u] (до этого счётчик времени увеличивается на 1). В строках 3-7 просматриваются смежные с и вершины; процедура DFS-Visit вызывается для тех из них, которые оказываются белыми к моменту вызова. После просмотра всех смежных с и вершин мы делаем вершину и чёрной и записываем в f[u] время этого события. Подсчитаем общее число операций при выполнении процедуры DFS. Циклы в строках 1-3 и 5-7 требуют О(С) времени (помимо вызовов DFS-Visit). Процедура DFS-Visit вызывается ровно один раз для каждой вершины (ей передаётся белая вершина, и она сразу же делает её серой). Во время выполнения DFS-Visit(u) цикл в строках 3-6 выполняется Аф[и] раз. Поскольку \Adj[v]\ = Q(E), vEV время выполнения строк 3-6 процедуры DFS-Visit составляет ©(E). В сумме получается время ©(С + Е). Свойства поиска в глубину. Прежде всего отметим, что подграф предшествования (составленный из деревьев поиска в глубину) в точности соответствует структуре рекурсивных вызовов процедуры DFS-Visit. Именно, и = ir[v] тогда и только тогда, когда произошёл вызов DFS-Visit(u) во время просмотра списка смежных с и вершин. Рис. 23.4 23.5 Свойства поиска в глубину, (а) Результат поиска (в обозначениях рис. 23.4). (Ь) Промежутки между обнаружением и окончанием обработки для каждой из вершин, изображённые в виде прямоугольников. Стрелки указывают структуру деревьев посика в глубину, (с) Отмечены рёбра исходного графа с указанием их типов (рёбра дерева и прямые рёбра ведут вниз, обратные ведут вверх). Другое важное свойство состоит в том, что времена обнаружения и окончания обработки образуют правильную скобочную структуру (parenthesis structure). Обозначая обнаружение вершины и открывающийся скобкой с пометкой и, а окончание её обработки - закрывающейся с той же пометкой, то перечень событий будет правильно построенным выражением в том смысле (скобки с одинаковыми пометками считаем парными). Например, поиску в глубину на рис. 23.5 (а) соответствует расстановка скобок, изображённая на рисунке 23.5(b). Чтобы доказать эти и другие свойства, мы должны рассуждать по индукции. При этом, доказывая требуемое свойство рекурсивной процедуры DFS-Visit, мы предполагаем, что рекурсивные вызовы этой процедуры обладают выбранным свойством. Убедимся вначале, что вызов DFS-Visit(m) для белой вершины и делает чёрной эту вершину и все белые вершины, доступные из неё по белым путям (в которых все промежуточные вершины также белые), и оставляет серые и чёрные вершины без изменений. В самом деле, рекурсивные вызовы в строке 6 выполняются лишь для белых вершин, являющихся смежными с и. Если какая-то вершина w была закрашена в ходе этих вызовов, то (по индуктивному предположению) она была доступна по белому пути из одной из белых вершин, смежных с и, и потому доступна по белому пути из и. Напротив, если вершина w доступна по белому пути из и, то этот она доступна по белому пути из какой-то белой вершины v, смежной с и (посмотрим на первый шаг пути). Будем считать, что v - первая из таких вершин (в порядке просмотра в строке 3). В этом случае все вершины белого пути из v в w останутся белыми к моменту вызова DFS-Visit(u), поскольку они недоступны по белым путям из предшествующих v вершин (иначе w была бы также доступна). По индуктивному предположению w станет чёрной после вызова DFS-Visit(u). Кроме того, сама вершина и станет сначала серой, а потом чёрной. (Заметим, что мы могли бы сразу сделать её чёрной, поскольку программа никак не различает серые и чёрные вершины, однако это различие нам пригодится в дальнейшем.) Ясно также, что цвета серых и чёрных вершин остаются без изменений (поскольку это верно для рекурсивных вызовов по индуктивному предположению). |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||