Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. e = Q.get(); st[e.w] = e.v; typename Graph::adjIterator A(G, e.w); for (int t = A.beg(); !A.end() ; t = A.nxt()) if (ord[t] == -1)
while (! Q.empty()) { e = Q.get(); st[e.w] = e.v; typename Graph:: adjIterator A(G, e.w); for (int t = A.beg();! A.end(); t = A.nxt()) if (ord[t] == -1) { Q.put(Edge(e.w, t)); ord[t] = cnt++; } > } Как показано на рис. 18.21 и отмечено в главе 5, нет необходимости помещать в очередь ребро с такой же вершиной назначения, что и у хотя бы одного ребра, которое уже находится в очереди, поскольку правило FIFO гарантирует, что мы выполним обработку ребра, которое уже находится в очереди (и нанесем визит в соответствующую вершину), раньше, чем приступим к обработке нового в очереди ребра. Один из способов реализации такой стратегии заключается в том, чтобы использовать реализацию АТД очереди, по условиям которой такое дублирование запрещается стратегией игнорирования новых элементов (см. раздел 4.7). Другой способ предусматривает применение для этой цели глобального вектора маркирования вершин: вместо того, чтобы маркировать вершину в момент ее исключения из очереди как посещенную, мы делаем это в момент включения ее в очередь. Обнаружение у той или иной вершины такой маркировки (т.е., изменилось ли значение соответствующего ее элемента относительно начального сигнального значения) означает запрет на включение в очередь каких-либо других ребер, которые указывают на эту вершину. Это изменение, показанное в программе 18.9, позволяет получить программную реализацию поиска в ширину, по условиям которой в очереди никогда не бывает более V ребер (в каждую вершину ведет максимум одно ребро). Свойство 18.11. Поиск в ширину посещает все вершины и ребра графа за время, пропорциональное V2, в случае представления графа в виде матрицы смежности, и за время, пропорциональное V + Е, в случае представления графа в виде списков смежных вершин. Доказательство: Подобно тому, как мы поступали при доказательстве аналогичных свойств поиска в глубину, путем анализа программного кода мы обнаруживаем, что проверяем каждый элемент строки матрицы смежности или списка смежных вершин в точности один раз для каждой вершины, которую мы посещаем, следовательно, достаточно показать, что мы посетили каждую вершину. Теперь же для каждой связной компоненты рассматриваемый алгоритм сохраняет следующие инварианты: все вершины, на которые можно выйти из исходной вершины, (i) включены в дерево BFS, (ii) поставлены в очередь или (iii) достижимы из одной из вершин, установленных в очередь. Каждая вершина перемещается из (iii) в (ii) и в (i), а число вершин в (i) увеличивается при каждой итерации цикла; таким образом, в конечном итоге дерево BFS будет содержать все вершины, на которые можно выйти из исходной вершины. Это дает нам, как и в случае поиска в глубину, основание утверждать, что поиск в ширину представляет собой алгоритм, линейный по времени выполнения. ■ С помощью поиска в ширину мы можем решить задачи обнаружения остовного дерева, связных компонент, поиска вершин и ряд других базовых задач связности, которые были сформулированы и описаны в разделе 18.4, поскольку рассмотренные решения зависят только от способности алгоритма поиска анализировать каждый узел и каждое ребро, связанное с исходной точкой. Как мы скоре убедимся, поиски в ширину и в глубину
|