Часть 5. Алгоритмы на графах. сматриваемом случае используется реализация DenseGRAPH графа в виде матрицы смеж­ности из раздела 17.3

сматриваемом случае используется реализация DenseGRAPH графа в виде матрицы смеж­ности из раздела 17.3. На рис. 18.6 дается графическое представление процесса исследо­вания лабиринта, для которого используются стандартные чертежи графа.

Указанные рисунки служат иллюстрацией динамики рекурсивного метода DFS и его соответствия с исследованием лабиринта методом Тремо. Во-первых, вектор, проиндек­сированный вершинами, соответствует освещению перекрестков: когда мы обнаружива­ем ребро, ведущее к вершине, на которой мы только что побывали (т.е. " видим свет в конце коридора"), мы не производим рекурсивных вызовов, дабы следовать вдоль этого ребра (т.е. идти вдоль этого коридора). Во-вторых, механизм вызова-возврата функции этой программы является аналогом нити в лабиринте: когда мы обработаем все ребра, ин­цидентные некоторой вершине (исследуем все коридоры, исходящие от соответствующе­го перекрестка), мы возвращаемся (в обоих смыслах этого слова).

Программа 18.1. Поиск в глубину связной компоненты_____________________________

Класс DFS соответствует исследованию Тремо. Конструктор помечает как посещенные все вершины той же связной компоненты, в которой содержится v, через вызов рекурсивной функции searchC, которая обходит все вершины, смежные с v, подвергая их всех проверке, и вызывая саму себя для каждого ребра, которое ведет из v в непомеченную вершину. Клиентские программы могут воспользоваться функцией count для вычисления числа посещенных вершин и перегруженным оператором [], чтобы узнать, в какой последовательности алгоритм поиска посещал вершины.

#include < vector>

template < class Graph> class cDFS

{ int cnt;

const Graph & G; vector < int> ord; void searchC(int v) {

ord[v] = cnt++;

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

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

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

cDFS (const Graph & G, int v = 0): G{G), cnt(0), ord(G.V(), -1) { searchC(v); }

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

Подобно тому, как при обходе лабиринта мы дважды сталкиваемся с каждым кори­дором (по одному разу с каждого конца), так и в графе мы дважды сталкиваемся с каж­дым ребром (по одному разу в каждой его вершине). При проведении исследования Тре­мо мы открываем двери в обоих концах коридора. Применяя поиск в глубину к неориентированному графу, мы проверяем оба представления каждого ребра. Если мы встречаем ребро v-w, то либо совершаем рекурсивный вызов (если вершина w не поме­чена), либо пропускаем это ребро (если w помечена). Когда мы встретим это же ребро во второй раз, на этот раз с противоположной ориентацией, то есть w-v, мы его игно­рируем, поскольку вершину назначения v мы уже определенно посещали (первый раз, когда сталкивались с этим ребром).

Глава 18. Поиск на графе

РИСУНОК 18.6. ПОИСК В ГЛУБИНУ

Данные диаграммы представляют собой графическое представление процесса, изображенного на рис. 18.5, на котором показано дерево рекурсивных вызовов поиска в глубину в его развитии. Ребра графа, выделенные толстыми жирными линиями, соответствуют ребрам в дереве DFS, показанном справа от каждой диаграммы графа. Заштрихованные ребра — это ребра, намеченные для включения в дерево на следующих шагах. На ранних стадиях (слева) выполнения алгоритма дерево растет вниз в виде прямой линии, что соответствует рекурсивным вызовам для вершин О, 2, 6 и 4 (слева). Затем мы выполняем рекурсивные вызовы для вершины 3, затем для вершины 5 (справа, две верхних диаграммы), после чего возвращаемся из этих вызовов, чтобы сделать очередной рекурсивный вызов для вершины 7 из вершины 4 (справа, вторая снизу) и для 1 из 7 (справа снизу).

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

Одно из различий между поиском в глубину, каким он реализован в программе 18.1, и исследованием Тремо, каким оно представлено на рис. 18.2 и 18.3, заслуживает того, чтобы потратить некоторое время на его изучение, хотя во многих контекстах оно не иг­рает никакой роли. Когда мы перемещаемся из вершины v в вершину w, мы не прове­ряем никаких элементов в матрице связности, которые соответствуют ребрам, ведущим из вершины w в другие вершины графа. В частности, мы знаем, что существует ребро из v в w и оно будет проигнорировано, когда мы на него выйдем (поскольку v помечена как посещенная вершина). Подобное решение приходится принимать в моменты, которые от­личаются от ситуаций, имеющих место во время проведения исследований Тремо, когда мы открываем дверь, соответствующую ребру, идущему из v в w, когда мы попадаем в

вершину w из v в первый раз. Если бы мы закрывали эти двери во время входа и открывали во время вы­хода (обозначив соответствующий коридор за счет протягивания вдоль него нити), то в этом случае мы бы имели точное соответствие между поиском в глу­бину и исследованием Тремо.

На рис. 18.6 показано дерево рекурсивных вызо­вов, соответствующее рис. 18.5, в динамике его раз­вития. Это дерево рекурсивных вызовов, известное как дерево DFS, обеспечивает структурное описание процесса поиска. Как следует из раздела 18.4, дере­во DFS, если оно наращивается должным образом, представляет собой полное описание динамики поис­ка в дополнение к только что описанной структуре вызовов.

Порядок обхода вершин зависит не только от графа, но и от его представления и реализации АТД. Например, на рис. 18.7 показана динамика поиска при использовании класса SparseMultiGRAPH из раздела 17.4 для реализации представления графа в виде списков смежных вершин. В случае представле­ния графа в виде матрицы смежности мы проводим исследование ребер, инцидентных каждой вершине, в цифровой последовательности. Что же касается представления графа в виде списков смежных вер­шин, то мы проводим их исследование в том поряд­ке, в каком они выступают в списках. Это различие приводит к совершенно другой динамике рекурсив­ных поисков, поскольку отличаются последователь­ности, в которых ребра появляются в списках (что имеет место, например, когда построение одного и того же графа производится путем вставки ребер в различном порядке). Обратите внимание на то обсто­ятельство, что наличие параллельных ребер не име-