Программа 18.3. Производный класс поиска в глубину

Данный программный код демонстрирует, как строится производный класс DFS остового дерева на основе базового класса, определение которого дано в разделе 18.2. Конструктор

РИСУНОК 18.8. ПОИСК НА ГРАФЕ

Таблица в нижней части рисунка содержит метки вершин (содержимое вектора ord) во время обычного поиска на графе, который показан в верхней части рисунка. Сначала функция GRAPHsearch из программы 18.2 отменяет старые метки всех вершин, устанавливая метки -1 всем вершинам (в таблице проставлены звездочки (*)). Затем она вызывает функцию search для фиктивного ребра 0-0, которая помечает все вершины, содержащиеся в той же компоненте, что и 0 (второй ряд таблицы), назначая им неотрицательные значения (в таблице проставлены 0). В рассматриваемом примере она помечает вершины 0, 1, 4 и 9 значениями от 0 до 3 в этом же порядке. Далее она производит просмотр слева направо, в результате которого находит неотмеченную вершину 2 и вызывает функцию search для фиктивного ребра 2-2 (третий ряд таблицы). Упомянутая функция search помечает семь вершин, содержащиеся в той же компоненте, что и 2. Продолжая просмотр слева направо, она вызывает search для ребра 8-8; в результате этого вызова помечаются вершины 8 и 11 (нижний ряд таблицы). И, наконец, функция GRAPHsearch завершает поиск, убедившись в том, что все вершины от 9 до 12 помечены.

Часть 5. Алгоритмы на графах

template < class Graph> class DFS: public SEARCH< Graph> { vector< int> st; void searchC(Edge e) { int w = e.w;

ord[w] = cnt++; st[e.w] = e.v;

typename Graph:: adjIterator A(G, w);

for (int t = A.beg();! A.end(); t = A.nxt())

if (ord[t] == -1) searchC(Edge(w, t)); } public:

DFS(const Graph & G): SEARCH< Graph> (G),

st(G.V(), -1) { search(); } int ST(int v) const { return st[v]; } };

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

Доказательство: Проводится методом индукции по числу связных компонент. ■

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

Свойство 18.3: Поиск в глубину на графе, представленном матрицей смежности, требу­ет времени, пропорционального V².

Доказательство: Рассуждения, аналогичные доказательству свойства 18.1, показывают, что функция searchC не только маркирует все вершины, связанные с исходной вер­шиной, но и вызывает сама себя в точности один раз для такой вершины (чтобы ее пометить). Рассуждения, аналогичные доказательству свойства 18.2, показывает, что вызов функции search приводит к вызову функции searchC для каждой вершины в точ­ности один раз. В функции searchC итератор проверяет каждый элемент строки вер­шины в матрице смежности. Другими словами, поиск проверяет каждый элемент мат­рицы смежности в точности один раз. ■

Свойство 18.4: Поиск в глубину на графе, представленного списками смежных вершин, тре­бует времени, пропорционального V+ Е.

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

Основной вывод, который следует из свойства 18.3 и 18.4, заключается в том, что вре­мя выполнения поиска в глубину линейно зависит от размеров структуры данных, исполь­зуемой для представления графа. В большинстве ситуаций вполне оправданно считать, что