Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Обобщенный поиск на графах
|
|
Поиски в ширину и в глубину представляют собой фундаментальные и весьма важные методы, которые лежат в основе многочисленных алгоритмов обработки графов. Зная их основные свойства, мы сможем перейти на более высокий уровень абстракции, на котором мы обнаруживаем, что оба метода суть частные случаи обобщенной стратегии перемещения по графу, именно той, которая была заложена нами в реализацию поиска в ширину (программа 18.9).
Основной принцип достаточно прост: мы снова обращаемся к описанию поиска в ширину из раздела 18.6, но теперь вместо понятия очередь (queue) мы употребляем обобщенный термин бахрома (fringe) для описания множества ребер, которые являются кандидатами для следующего включения в дерево поиска. Мы немедленно приходим к общей стратегии поиска связной компоненты графа. Начав с петли исходной вершины в бахроме и пустого дерева, до тех пор, пока бахрома не станет пустой, выполняйте следующую операцию:
Возьмите очередное ребро из бахромы и перенесите его в дерево. Если вершина, в которую оно ведет, еще не посещалась, пройдите на эту вершину и поместите в бахрому все ребра, которые ведут из этой вершины в вершины, на которых вы еще не были.
Эта стратегия описывает семейство алгоритмов поиска, которые обеспечивают посещение всех вершин и ребер связного графа независимо от того, какой тип обобщенной очереди используется для хранения ребер в бахроме.
Когда для реализации бахромы используется очередь, мы получаем поиск в ширину, который рассматривается в разделе 18.6. Когда для реализации бахромы используется стек, получается поиск в глубину. На рис. 18.25, который мы предлагаем сравнить с рис. 18.6 и 18.21, этот эффект представлен во всех деталях.
Часть 5. Алгоритмы на графах
|
РИСУНОК 18.25 АЛГОРИТМ ПОИСКА В ГЛУБИНУ, ПОСТРОЕННЫЙ НА БАЗЕ СТЕКА
Вместе с рис. 18.21 данный рисунок служит доказательством того, что поиски в ширину и в глубину отличаются друг от друга только структурой данных, положенной в их основу. Для поиска в ширину мы использовали очередь, тогда как для поиска в глубину — стек. Выполнения этого вида поиска начинается с просмотра всех вершин, смежных с отправной вершиной (вверху слева). Затем мы перемещаем ребро О- 7 из стека в дерево и заталкиваем в стек инцидентные ему ребра 7-1, 7-4 и 7-6, ведущие в вершины, которых еще нет в дереве (вторая диаграмма сверху слева). Дисциплина обслуживания LIFO предполагает, что когда мы помещаем то или иное ребро в стек, любые ребра, ведущие в ту же вершину, устаревают и игнорируются, когда появляются в вершине стека. Эти ребра показаны на рисунке в серых тонах. В третьих, мы переносим ребро 7-6 из стека в дерево и заталкиваем инцидентные ему ребра в стек (третья диаграмма сверху слева). Затем мы извлекаем ребро 4-6 из стека и помещаем в него инцидентные ему ребра, два из которых приводят нас к новым вершинам (диаграмма внизу слева). В завершение поиска мы извлекаем из стека оставшиеся ребра, при этом полностью игнорируем " серые" ребра, когда они всплывают в верхушку стека (справа).
Глава 18. Поиск на графе
|
| Доказательство эквивалентности рекурсивного поиска в глубину и поиска в глубину, в основу которого положен стек, представляет собой интересное упражнение, предусматривающее удаление рекурсии, в процессе которого мы фактически преобразуем стек, лежащий в основе рекурсивной программы, в стек, реализующий бахрому (см. упражнение 18.63). Порядок просмотра, осуществляемый поиском в глубину и представленный на рис. 18.25, отличается от порядка просмотра, показанного на рис. 18.6, только тем, что дисциплина обслуживания, реализуемая стеком, требует, чтобы мы проверяли ребра, инцидентные каждой вершине, в порядке, обратном тому, в котором они размещены в матрице смежности (или в списках смежных вершин). Определяющее обстоятельство заключается в том, что если мы заменим очередь, которая является структурой данных в программе 18.8, на стек (что легко сделать, поскольку интерфейсы АТД этих двух структур данных отличаются только именами функций), то мы поменяем ориентацию этой программой с поиска в ширину на поиск в глубину. Этот обобщенный метод, как следует из раздела 18.7, может оказаться не таким эффективным, как хотелось бы, поскольку бахрома оказывается загроможденной ребрами, указывающими на вершины, которые уже были перенесены в дерево, когда данное ребро находилось в бахроме. В случае очередей FIFO нам удается избежать подобной ситуации благодаря маркировке вершин назначения в момент установки их в очередь. Мы игнорируем ребра, ведущие в вершины, находящиеся в накопителе, поскольку знаем, что |
они никогда не будут использованы: старое ребро уходит из очереди (и посещенная вершина) раньше, чем новое (см. программу 18.9). Что касается реализации со стеком, то в этом случае мы заинтересованы в обратном: когда в бахрому нужно поместить ребро с той же вершиной назначения, что и ребро, которое уже в ней находится, мы знаем, что старое ребро никогда не будет использовано, поскольку новое ребро покинет стек (равно как и посещенная вершина) раньше старого. Чтобы охватить эти два крайних случая и обеспечить возможность реализации бахромы, которая может воспользоваться какой-нибудь другой стратегией, блокирующей попадание в бахрому ребер, указывающих на ту же вершину, что и ребра в бахроме, мы скорректируем нашу обобщенную схему следующим образом:
Возьмите очередное ребро из бахромы и перенесите его в дерево. Посетите вершину, в которую оно ведет, и поместите все ребра, которые выходят из этой вершины, в бахрому, руководствуясь стратегией замены в бахроме, которая требует, чтобы никакие два ребра в бахроме не указывали на одну и ту же вершину.
Стратегия отсутствия дубликатов вершин назначения в бахроме позволяет отказаться от проверки, имело ли место посещение вершины назначения ребра, покидающего очередь. В случае поиска в ширину мы
РИСУНОК 18.26. ТЕРМИНОЛОГИЯ ПОИСКА НА ГРАФЕ
Во время поиска на графе мы поддерживаем дерево поиска (черный цвет) и бахрому (серый цвет) из ребер, которые являются кандидатами на следующее включение в дерево. Любая вершина либо входит в состав дерева (черный цвет), либо в бахрому (серый цвет), либо остается непроверенной (белый цвет). Вершины дерева соединены древесными ребрами, а каждая вершина накопителя соединена ребром накопителя с некоторой вершиной дерева.
Часть 5, Алгоритмы на графах
РИСУНОК 18.27. СТРАТЕГИИ ПОИСКА НА ГРАФЕ
Этот рисунок иллюстрирует различные возможности при выборе следующего действия поиска, показанного на рис. 18.26. Мы переносим вершину из бахромы в дерево (из центра колеса, изображенного вверху справа) и проверяем все ее ребра, помещая ребра, ведущие в непроверенные вершин, в бахрому и применяя при этом правило замещения, чтобы решить, следует ли ребра, указывающие на вершины в бахроме, пропустить или заменить ими ребро, которое присутствует в бахроме и указывает на ту же самую вершину. В описке в глубину мы всегда заменяем старые ребра, а в поиске в ширину — всегда игнорируем новые ребра; по условиям других стратегий мы заменяем одни ребра и пропускаем другие.
используем реализацию очереди в сочетании со стратегией игнорирования новых элементов; что касается поиска в глубину, то нам нужен стек в сочетании со стратегией игнорирования старых элементов, в то же время любая обобщенная очередь и любая стратегия замен все еще дает эффективный метод просмотра всех вершин и ребер графа за линейное время, при этом необходимо дополнительное пространство памяти, пропорциональное V. Рисунок 18.27 представляет собой схематическую иллюстрацию этих различий. В нашем распоряжении имеется семейство стратегий поиска на графе, в число которых входит как BFS (поиск в ширину), так и DFS (поиск в глубину), члены которого отличаются друг от друга только реализацией обобщенной очереди. Как будет вскоре показано, это семейство охватывает другие многочисленные классические алгоритмы обработки графов.
Программа 18.10 представляет реализацию, основанную на этих идеях, для графов, представленных списками смежных вершин. Она помещает ребра бахромы в обобщенную очередь и использует обычные векторы, индексированные именами вершин, для идентификации вершин в бахроме, так что она может воспользоваться явной операцией АТД update (обновить), всякий раз, когда сталкивается с другим ребром, ведущим в вершину в бахроме. Реализация АТД способна выбирать, игнорировать ли ей новое ребро или заменить им старое ребро.
Программа 18.10 Обобщенный поиск на графе_________________________________
Данный класс просмотра обобщает алгоритмы DFS и BFS и поддерживает другие алгоритмы обработки графов (см. раздел 21.2, в котором обсуждаются эти алгоритмы и альтернативные реализации). Он поддерживает обобщенную очередь ребер, получившую название бахрома (fringe). Мы инициализируем бахрому петлей исходной вершины; затем, пока бахрома не пуста, мы переносим ребро е из бахромы в дерево (присоединение к e.v) и проводим просмотр списка смежных вершин вершины e.w, во время которого помещаем непросмотренные вершины в бахрому и вызываем функцию update при появлении новых ребер, указывающих на вершины, зафиксированные в бахроме.
Этот программный код позволяет использовать векторы ord и st для того, чтобы никакие два ребра в бахроме не указывали на одну и те же вершину. Вершина v является