Функции АТД поиска на графе

Метод маркирования не задан в этом описании, но в большинстве случаев мы при­меняем тот же метод, который был использован в реализациях поиска в глубину в раз­деле 18.2: мы инициализируем все элементы приватного вектора, индексированного име­нами вершин, отрицательным целым числом и помечаем вершины, присваивая соответствующим компонентам вектора неотрицательные значения. Использование этой процедуры сводится к установке значения всего лишь одного разряда (знакового) мет­ки; в условиях большинства реализаций в векторе хранится также и другая информация, имеющая отношение к помеченным вершинам (например, в реализации из раздела 18.2 это порядок, в котором маркируются вершины). Не определен также метод поиска вер­шин в следующей связной компоненте, но мы чаще всего применяем просмотр этого век­тора в порядке возрастания индекса.

Программа 18.2. Поиск на графе___________________________________________

Данный базовый класс предназначен для обработки графов, которые могут оказаться несвязными. Производные классы должны дать определение функции searchC, которая, будучи вызванной с петлей вершины v в качестве второго аргумента, устанавливает ord[t] в cnt++ для каждой вершины t, содержащейся в той же связной компоненте, что и вершина v. Чаще всего конструкторы в производных классах вызывают функцию search, которая, в свою очередь, вызывает searchC один раз для каждой связной компоненты графа.

template < class Graph> class SEARCH {

protected: const Graph & G; int cnt;

vector < int> ord; virtual void searchC(Edge) = 0; void search() { for (int v = 0; v < G.V(); v++)

if (ord[vj == -1) searchC (Edge (v, v)); } public: SEARCH (const Graph & G): G(G),

ord(G.V(), -1), cnt(0) { }

int operator[](int v) const { return ord[v]; } };

Мы передаем в функцию поиска ребро (используя фиктивную петлю в первом вызо­ве для каждой связной компоненты) вместо того, чтобы задавать ей его вершину назна­чения, ибо ребро говорит нам, как выйти в эту вершину. Если мы знаем ребро, то это равносильно знанию, какой коридор ведет к конкретному перекрестку в лабиринте. Эта информация полезна во многих классах DFS. Если мы просто отслеживаем, в какие вер­шины мы нанесли визит, то от этой информации мало толку, в то же время более инте­ресные задачи требуют знания места, откуда мы пришли.

Программа 18.2 представляет собой реализацию, которая служит иллюстрацией этих возможностей. На рис. 18.8 представлен пример, который показывает, как отражается посещение каждой вершины на состоянии вектора ord любого производного класса. Как правило, рассматриваемые производные классы также исследуют все ребра, инцидентные каждой посещенной вершине. В таких случаях знание того факта, что мы посетили все вершины, говорит нам, что мы также посетили все ребра, как и в случае обхода Тремо.