Часть 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. Поиск в ширину посещает все вершины и ребра графа за время, пропор­циональное V², в случае представления графа в виде матрицы смежности, и за время, про­порциональное V + Е, в случае представления графа в виде списков смежных вершин.

Доказательство: Подобно тому, как мы поступали при доказательстве аналогичных свойств поиска в глубину, путем анализа программного кода мы обнаруживаем, что проверяем каждый элемент строки матрицы смежности или списка смежных вершин в точности один раз для каждой вершины, которую мы посещаем, следовательно, до­статочно показать, что мы посетили каждую вершину. Теперь же для каждой связной компоненты рассматриваемый алгоритм сохраняет следующие инварианты: все верши­ны, на которые можно выйти из исходной вершины, (i) включены в дерево BFS, (ii) поставлены в очередь или (iii) достижимы из одной из вершин, установленных в оче­редь. Каждая вершина перемещается из (iii) в (ii) и в (i), а число вершин в (i) увели­чивается при каждой итерации цикла; таким образом, в конечном итоге дерево BFS будет содержать все вершины, на которые можно выйти из исходной вершины. Это дает нам, как и в случае поиска в глубину, основание утверждать, что поиск в шири­ну представляет собой алгоритм, линейный по времени выполнения. ■

С помощью поиска в ширину мы можем решить задачи обнаружения остовного де­рева, связных компонент, поиска вершин и ряд других базовых задач связности, которые были сформулированы и описаны в разделе 18.4, поскольку рассмотренные решения за­висят только от способности алгоритма поиска анализировать каждый узел и каждое реб­ро, связанное с исходной точкой. Как мы скоре убедимся, поиски в ширину и в глубину