Часть 5. Алгоритмы на графах. Сочетание программы 18.10 с абстракцией обобщенной очереди дает нам в руки уни­версальный и гибкий механизм поиска на графе

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

Первая альтернативная стратегия основана на использовании рандомизированной оче­реди (randomized queue) (см. раздел 4.1). Из рандомизированных очередей элементы удаля­ются случайным образом: любой элемент такой структуры данных может с равной веро­ятностью быть удален. Программа 18.11 представляет собой реализацию, которая обеспечивает упомянутую функциональность. Если мы используем этот программный код для реализации АТД обобщенной очереди, то получаем алгоритм случайного поиска на графе, по условиям которого любая вершина, находящаяся в накопителе, с равной веро­ятностью может стать следующей вершиной, включенной в дерево. Выбор ребра (ведуще­го в эту вершину), добавляемого в дерево, зависит от реализации операции обновления (update). Реализация, представленная программой 18.11, не производит обновления дан­ных, таким образом, каждая вершина из бахромы включается в дерево вместе с ребром, которое послужило причиной ее переноса в бахрому. С другой стороны, мы могли бы избрать стратегию " обновлять всегда" (которая предполагает добавление в дерево после­днего ребра, если оно направлено в какую-либо из вершин, помещенных в бахрому), либо стратегию случайного выбора.

Другая стратегия, играющая исключительно важную роль в изучении алгоритмов об­работки графов, поскольку служит основой целого ряда классических алгоритмов, кото­рые будут изучаться в главах 20-22, - это использование для бахромы АТД очереди с при­оритетами (priority queue) (см. главу 9). Мы присваиваем определенное значение приоритета каждому ребру, обновляем его соответствующим образом и выбираем ребро с наивысшим приоритетом для очередного включения в дерево. Подробный анализ этой формулировки проводится в главе 20. Операции по поддержке очереди по приоритетам требуют больших затрат, чем аналогичные операции в отношении стеков и очередей, по­скольку для этого необходимо выполнять операции сравнения элементов очереди, но в то же время они могут поддерживать значительно более широкий класс алгоритмов по­иска на графах. Как мы увидим далее, некоторые из наиболее важных задач обработки графов можно решать путем выбора подходящей процедуры назначения приоритетов в рамках обобщенного поиска на графе, построенного на базе очереди по приоритетам.

Программа 18.11. Реализация рандомизированной очереди______________________

Когда мы удаляем элемент из этой структуры данных, в равной степени вероятно, что это один из элементов, сохраняемых на текущий момент в этой структуре данных. Можно использовать этот программный код, реализующий АТД обобщенной очереди для поиска на графе, для поиска на графе в " стохастическом" режиме (см. рассуждения по тексту раздела).

template < class Item> class GQ

{ private:

vector< Item> s; int N; public:

GQ(int maxN): s(maxN+l), N(0) { } int empty () const { return N == 0; }