Поиск на графе

Поиск в глубину

Метод Тремо интересен тем, что он непосредствен -но приводит к классическому рекурсивному методу обхода графов: посетив конкретную вершину, мы помечаем ее как посещенную, а затем рекурсивно посещаем все смежные с ней непомеченные вершины. Такой метод уже был кратко рассмотрен в и и использовался для решения задачи нахождения путей в — он называется поиск в глубину (DFS — depth-first search). Это один из наиболее важных алгоритмов из применяемых нами. Метод DFS с виду прост, поскольку основан на знакомой идее, и его нетрудно реализовать, но на самом деле это очень гибкий и мощный алгоритм, который можно применять для решения множества трудных задач обработки графов.

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

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

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

Программа 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]; }
    };
      

(рис 18.5) Трасса работы DFS

Здесь показан порядок, в котором алгоритм поиска в глубину проверяет ребра и вершины в представлении матрицей смежности графа, изображенного на рис 18.2 и рис 18.3(вверху), и содержимое вектора ord (справа) при выполнении поиска (звездочки означают -1 для не посещенных вершин). Каждому ребру графа соответствуют две строки, по одной на каждое направление. Величина отступа определяет уровень рекурсии.

(рис 18.6) Поиск в глубину

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

Между поиском в глубину, реализованным в программе 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) Трасса DFS (списки смежности)

Здесь показан порядок просмотра ребер и вершин при поиске в глубину на графе с рис 18.5, представленном списками смежности.

Несмотря на все эти варианты, остается неизменным основное свойство алгоритма поиска в глубину: он посещает все ребра и все вершины, соединенные с исходной вершиной, независимо от порядка просмотра ребер, инцидентных каждой вершине. Это непосредственно следует из леммы 18.1, поскольку доказательство этой леммы не зависит от порядка открытия дверей на любом заданном перекрестке. Все изучаемые нами алгоритмы на основе DFS обладают этим очень важным свойством. Хотя динамика выполнения может существенно различаться в зависимости от представления графа и деталей реализации поиска, рекурсивная структура позволяет сделать правильные выводы о самом графе независимо от способа его представления и от порядка просмотра ребер, инцидентных каждой вершине.

Упражнения

18.4. Добавьте в программу 18.1 общедоступную функцию-член, которая возвращает размер связного компонента, просматриваемого конструктором.

18.5. Напишите клиентскую программу наподобие программы 17.6, которая просматривает граф, введенный из стандартного ввода, использует программу 18.1 для выполнения поиска из каждой вершины и выводит представление родительскими ссылками каждого остовного леса. Воспользуйтесь реализацией DenseGRAPH АТД графа из .

18.6. В стиле рис 18.5 представьте трассу вызовов рекурсивной функции, выполненных при построении объекта DFS<DenseGRAPH для графа

0-20-51-23-44-53-5.

Начертите соответствующее дерево рекурсивных вызовов DFS.

18.7. В стиле рис 18.6 продемонстрируйте процесс поиска для примера из упражнения 18.6.

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

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

Найти непомеченную вершину (начальная вершина).

Посетить (и пометить как посещенные) все вершины в связном компоненте, который содержит начальную вершину.

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

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

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

Программа 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[v] == -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]; }
    };
      

(рис 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 помечены, и завершает поиск.

Программа 18.3 — пример, который показывает, как можно получить класс DFS для определения остовного леса, производный от базового класса SEARCH из программы 18.2. В производный класс добавлен приватный вектор st для хранения представления дерева родительскими ссылками, которое инициализируется в конструкторе. Кроме того, в этом классе определена функция searchC, которая совпадает с функцией searchC из программы 18.1, за исключением того, что она принимает в качестве аргумента ребро v-w и заносит в st[w] значение v. И, наконец, добавлена общедоступная функция-член, которая позволяет клиентам определять родителя любой вершины. Остовные леса применяются во многих приложениях, но в этой главе они нужны нам в основном для понимания динамического поведения DFS, о чем пойдет речь в разделе 18.4.

В связном графе конструктор из программы 18.2 вызывает функцию searchC всего один раз (для ребра 0-0) , после чего обнаруживает, что все остальные вершины помечены. В графе, состоящем из более чем одного связного компонента, конструктор последовательно просматривает все связные компоненты. Поиск в глубину является первым из нескольких методов, который будет применяться для поиска связных компонентов графа. Но независимо от метода (и представления графа), программа 18.2 представляет собой эффективный метод просмотра всех вершин графа.

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

Доказательство. Методом индукции по количеству связных компонентов. $$$\blacksquare$$$

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

Данный код демонстрирует порождение производного от DFS класса для построения остовного дерева на основе базового класса, определенного в разделе 18.2. Конструктор строит представление леса в векторе st (родительские ссылки) и в векторе ord (из базового класса). Клиенты могут использовать объект DFS для определения родителя любой заданной вершины леса (ST) или позиции любой заданной вершины при прямом обходе леса (перегруженный оператор []). Свойства таких лесов и их представлений будут рассмотрены в разделе 18.4.

  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.3. Поиск в глубину на графе, представленном матрицей смежности, требует времени, пропорционального V².

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

Лемма 18.4. Поиск в глубину на графе, представленном списками смежности, требует времени, пропорционального V + E.

Доказательство. Из приведенных выше рассуждений следует, что мы вызываем рекурсивную функцию в точности V раз (отсюда слагаемое V ), а также проверяем каждый элемент в списке смежности (отсюда слагаемое E ). $$$\blacksquare$$$

Основной вывод из лемм 18.3 и 18.4 заключается в том, что время выполнения поиска в глубину линейно зависит от размера структуры данных, используемой для представления графа. В большинстве ситуаций можно считать, что время выполнения DFS линейно зависит от размеров самого графа: в случае насыщенного графа (число ребер которого пропорционально V² ) этот результат справедлив для любого представления, а в случае разреженного графа предполагается представление списками смежности. Вообще-то обычно считается, что время выполнения DFS линейно зависит от E. Формально это утверждение неверно — для разреженных графов, представленных матрицей смежности, или для крайне разреженных графов, для которых E << Vи большая часть вершин изолирована; однако обычно нетрудно избежать первой ситуации и удалить изолированные вершины во второй ситуации (см. упражнение 17.34).

Как будет показано ниже, эти рассуждения применимы к любому алгоритму, для которого выполняются некоторые основные свойства DFS. Если алгоритм помечает каждую вершину и проверяет все инцидентные ей вершины (и выполняет другую работу, на выполнение которой для одной вершины требуется время, ограниченное некоторой константой), то для него эти свойства выполняются. В более общей формулировке это звучит так: если время, затрачиваемое на обработку каждой вершины ограничено некоторой функцией f (V, E), то время поиска гарантированно пропорционально E + f (V, E). В разделе 18.8 мы увидим, что поиск в глубину является одним из алгоритмов семейства, которому присущи как раз такие свойства; в лекциях 19—22 мы увидим, что алгоритмы этого семейства лежат в основе значительной части программ, которые рассматриваются в данной книге.

Многие изучаемые нами программы обработки графов представляют собой реализации АТД для каких-то конкретных задач; в них мы разрабатываем класс, выполняющий базовый поиск для вычисления структурной информации в других векторах, индексированных именами вершин. Такой класс можно породить от класса из программы 18.2 или, в более простых случаях, просто заново реализовать поиск. Многие из наших классов обработки графов имеют такой характер, поскольку, при выполнении поиска на графе мы, как привило, получаем представление и о его структуре. Обычно мы добавляем код в функцию поиска, которая выполняется после пометки всех вершин, вместо того чтобы работать с более общим алгоритмом поиска (например, который вызывает указанную функцию при каждом посещении вершины) — просто чтобы сделать код компактным и замкнутым. Построение более общего механизма АТД, который позволяет клиентам обрабатывать все вершины с помощью клиентских функций, является очень полезной практикой (см. упражнения 18.13 и 18.14).

В разделах 18.5 и 18.6 мы познакомимся с многочисленными функциями обработки графов, основанными на DFS. В разделах 18.7 и 18.8 мы рассмотрим другие реализации функции search и ряд других функций обработки графов, основанных на этих реализациях. Мы не встраиваем такой уровень абстракции в наш код, но мы стараемся четко показать базовую стратегию поиска на графе, которая лежит в основе разрабатываемого алгоритма. Например, мы применяем термин класс DFS для любой реализации, основанной на рекурсивной схеме DFS. Примерами классов DFS могут служить класс программ для поиска простого пути (программа 17.16) и класс остовного леса (программа 18.3).

Многие функции обработки графов основаны на использовании векторов, индексируемых именами вершин. Обычно такие векторы включаются в реализации классов как приватные члены данных и содержат информацию о структуре графов (определяемую во время поиска), которая и позволяет решить текущую задачу. Примерами таких векторов могут служить вектор deg в программе 17.11 и вектор ord в программе 18.1. Некоторые из реализаций, которые мы рассмотрим, используют сразу несколько векторов для изучения сложных структурных свойств.

При написании функций поиска на графах мы будем придерживаться следующего соглашения: вначале все векторы, индексируемые именами вершин, очищаются значением — 1, а функции поиска будут заносить во все элементы, соответствующие посещенным вершинам, неотрицательные значения. Любой такой вектор может играть роль вектора ord (пометка вершин как посещенных) в программах 18.2 и 18.3. Если функция поиска на графе основана на использовании или вычислении вектора, индексируемого именами вершин, то зачастую мы просто реализуем поиск и используем этот вектор для пометки вершин, а не порождаем класс от базового класса SEARCH и не задействуем вектор ord.

Конкретные результаты поиска на графе зависят не только от природы функции поиска, но и от представления графа и даже от порядка просмотра вершин функцией search. Для определенности в примерах и упражнениях в данной книге мы будем употреблять термин стандартный DFS по спискам смежности (standard adjacency-lists DFS) для обозначения процесса вставки последовательности ребер в АТД графа, реализованный на основе представления списками смежности (программа 17.9) с последующим выполнением DFS — например, с помощью программы 18.3. В случае представления матрицей смежности порядок вставки ребер не влияет на динамику поиска, но мы будем использовать параллельный термин стандартный DFS по матрице смежности (standard adjacency-matrix DFS) для обозначения процесса вставки последовательности ребер в АТД графа, реализованный на основе представления графа матрицей смежности (программа 17.7) с последующим выполнением DFS — например, с помощью программы 18.3.

Упражнения

18.8. В стиле рис. 18.5 рис 18.5 приведите трассу вызовов рекурсивной функции, выполняемых при стандартном DFS по матрице смежности для графа

3-71-47-80-55-23-82-90-64-92-66-4.

18.9. В стиле рис. 18.7 рис 18.7 приведите трассу вызовов рекурсивной функции, выполняемых при стандартном DFS по матрице смежности для графа

3-71-47-80-55-23-82-90-64-92-66-4.

18.10. Измените реализацию АТД графа в виде матрицы смежности (программе 17.7), чтобы в ней использовалась фиктивная вершина, связанная со всеми другими вершинами. Напишите реализацию упрощенного DFS, используя это изменение.

18.11. Выполните упражнение 18.10 для реализации АТД списками смежности (программа 17.9).

18.12. Существует 13! различных перестановок вершин в графе, показанном на рис 18.8. Какая часть этих перестановок может описывать порядок посещения вершин графа программой 18.2?

18.13. Напишите реализацию клиентской функции АТД графа, которая вызывает указанную клиентом функцию для каждой вершины графа.

18.14. Напишите реализацию клиентской функции АТД графа, которая вызывает указанную клиентом функцию для каждого ребра графа. Такая функция может оказаться приемлемой альтернативой функции GRAPHedges (см. программу 17.2).

Свойства лесов DFS

Как было сказано в разделе 18.2, деревья, которые описывают рекурсивную структуру вызовов функции DFS, позволяют понять, как выполняется поиск в глубину. В данном разделе мы ознакомимся со свойствами этого алгоритма, изучая свойства деревьев DFS.

Если добавить в дерево DFS дополнительные узлы для пропусков рекурсивных вызовов в случае уже посещенных вершин, то получится компактное представление о динамике поиска в глубину, как на рис 18.9. Эта древовидная структура заслуживает подробного изучения. Она является представлением графа: каждой вершине дерева соответствует вершина графа, а каждому его ребру — ребро графа. Можно показывать или оба представления обрабатываемого ребра (по одному в каждом направлении), как показано в левой части рис 18.9, или только одно представление, как показано в центральной и правой частях рисунка. Первый вариант наглядно показывает, что алгоритм обрабатывает каждое ребро, а второй — что дерево DFS представляет собой просто еще одно представление графа. Прямой обход внутренних узлов дерева в прямом порядке посещает вершины в порядке их просмотра при поиске в глубину; более того, порядок посещения ребер при прямом обходе дерева совпадает с порядком просмотра ребер в графе алгоритмом DFS.

Вообще-то дерево DFS, показанное на рис 18.9, содержит ту же информацию, что и трасса на рис 18.5 или пошаговая иллюстрация обхода методом Тремо на рис 18.2 и рис 18.3. Ребра, ведущие к внутренним узлам, соответствуют ребрам (коридорам) к еще не посещенным вершинам (перекресткам); ребра, ведущие к внешним узлам, соответствуют случаям, когда DFS проверяет ребра, ведущие к уже посещенным вершинам (перекресткам); а заштрихованные узлы соответствуют ребрам к вершинам, для которых в данный момент выполняется рекурсивный поиск в глубину (когда мы открываем дверь в коридор, в котором дверь на противоположном конце уже открыта). При такой интерпретации прямой обход дерева сообщает нам ту же информацию, что и подробный способ обхода лабиринта.

Чтобы перейти к более сложным свойствам графов, разграничим ребра графа в соответствии с ролью, которую они играют в поиске. Имеются два различных класса ребер:

ребра, представляющие рекурсивные вызовы (древесные (tree) ребра);

ребра, соединяющие в дереве DFS вершину с ее предшественником, который не является ее родителем (обратные (back) ребра).

При изучении деревьев DFS для орграфов в мы рассмотрим и другие типы ребер — не только для учета направления ребер, но и потому, что в графе возможны ребра, которые идут поперек дерева и соединяют узлы, не являющиеся в этом дереве ни предками, ни потомками.

(рис 18.9) Различные представления дерева DFS

Если добавить в дерево рекурсивных вызовов DFSребра, которые мы проверяем, но не проходим, то получится полное описание процесса DFS (слева). У каждого узла дерева имеются потомки, представляющие все смежные с ним узлы в порядке их перебора алгоритмом DFS. Прямой обход дерева дает ту же информацию, что и рис 18.5: сначала мы проходим ребро ).

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

Поскольку существуют два представления каждого ребра графа, и каждое ребро соответствует ссылке в дереве DFS, мы разобьем все ссылки дерева на четыре класса, воспользовавшись прямыми номерами (preorder number) и родительскими ссылками (соответственно, в массивах ord и st), которые вычисляет код поиска в глубину. Будем называть ссылку из вершины v на w в дереве DFS, которая представляет ребро дерева, так:

древесная ссылка (tree link), если v не помечена;

родительская ссылка (parent link), если st[w] содержит v,

а ссылку из v на w, которая представляет обратное ребро, так:

обратная ссылка (back link), если ord[w] < ord[v];

нисходящая ссылка (down link), если ord[w] > ord[v].

Каждое древесное ребро в графе соответствует древесной ссылке и родительской ссылке в дереве DFS, а каждое обратное ребро в графе соответствует обратной ссылке и нисходящей ссылке в дереве DFS.

В графическом представлении DFS, показанном на рис 18.9, древесные ссылки указывают на светлые кружки, родительские ссылки — на серые кружки, обратные ссылки — на светлые квадратики, а нисходящие ссылки — на серые квадратики. Каждое ребро графа представлено либо одной древесной ссылкой и одной родительской ссылкой, либо одной нисходящей ссылкой и одной обратной ссылкой.

Эти термины достаточно запутанны, но их следует изучить. Например, учтите, что даже если родительские ссылки и обратные ссылки указывают на предков в дереве, они различны: родительская ссылка — это всего лишь другое представление древесной ссылки, а обратная ссылка дает новую информацию о структуре графа.

Приведенные выше определения предоставляют достаточно информации, чтобы провести различие между ссылкой древовидной структуры, родительской ссылкой, обратной ссылкой и нисходящей ссылкой в реализации класса DFS. Учтите, что условие представлена распечатка результатов классификации ссылок дерева DFS для всех ребер некоторого графа в порядке их рассмотрения алгоритмом DFS. Это еще одно полное представление базового процесса поиска, которое может служить промежуточным этапом между рисунками 18.5 и 18.9.

(рис 18.10) Трасса поиска в глубину (классификация ссылок дерева)

В данном варианте рис 18.5 приведена классификация ссылок в дереве DFS, соответствующих представлениям каждого ребра графа. Древесные ребра (которые соответствуют рекурсивным вызовам) представлены как древесные ссылки при первой встрече и как родительские ссылки при второй встрече, а обратные ребра — как обратные ссылки при первой встрече и как нисходящие ссылки при второй встрече.

Четыре описанных выше типа ссылок соответствуют четырем различным способам обработки ребер при поиске в глубину, которые были описаны (в терминах обхода лабиринта) в конце раздела 18.1. Древесная ссылка соответствует встрече первого из двух представлений древесного ребра при работе DFS, что приводит к рекурсивному вызову (к еще не просмотренным вершинам); родительская ссылка соответствует встрече с другим представлением древесного ребра (при просмотре списка смежности первым таким рекурсивным вызовом) и игнорированию этого ребра. Обратная ссылка соответствует встрече первого из двух возможных представлений обратного ребра, указывающего на вершину, для которой рекурсивный поиск еще не закончен; нисходящая ссылка соответствует встрече вершины, для которой рекурсивный поиск уже закончен. На рис 18.9 древесные и обратные ссылки соединяют светлые узлы, представляют первую встречу соответствующего ребра и входят в представление графа; родительские и нисходящие ссылки ведут в серые узлы и означают вторую встречу с соответствующим ребром.

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

Поиск на графе является обобщением обхода дерева. На дереве алгоритм DFS в точности эквивалентен рекурсивному обходу дерева; на графах он соответствует обходу остовного дерева этого графа, которое строится при выполнении поиска. Как мы уже знаем, конкретный вид дерева обход зависит от представления графа. Поиск в глубину соответствует прямому обходу дерева. В разделе 18.6 мы познакомимся с алгоритмом поиска на графе, который аналогичен обходу дерева по уровням, и выясним, как он соотносится с алгоритмом DFS, а в разделе 18.7 мы рассмотрим общую схему, которая охватывает все методы обхода.

При обходе графов с помощью DFS мы использовали вектор ort для присвоения вершинам прямых номеров в порядке начала их обработки. Вершинам можно присвоить и обратные номера (postorder numbers), т.е. номера в порядке завершения их обработки (непосредственно перед выходом из функции рекурсивного поиска). В процессе обработки графа выполняется не просто обход вершин — как мы вскоре увидим, прямая и обратная нумерация предоставляет сведения о глобальных свойствах графа, которые помогают справиться с решением некоторых задач. Для алгоритмов, рассматриваемых в данной главе, достаточно прямой нумерации, а обратная нумерация пригодится нам в последующих лекциях.

Мы описываем динамику поиска в глубину на неориентированных графах общего вида с помощью леса DFS (DFS forest), в котором каждое дерево DFS представляет один связный компонент графа. Пример леса DFS показан на рис 18.11.

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

(рис 18.11) Лес DFS

Лес DFS в верхней части рисунка соответствует поиску в глубину на графе, представленном матрицей смежности в нижней правой части рисунка. Граф состоит из трех связных компонентов, поэтому и лес содержит три дерева. Вектор ord содержит прямую нумерацию узлов дерева (порядок, в котором они просматриваются алгоритмом DFS), а вектор st содержит представление леса родительскими ссылками. Вектор cc связывает каждый компонент с индексом связного компонента (см. программу 18.4). Как и на рис 18.9, ребра, ведущие к кружкам, — это древесные ребра, а ребра, ведущие к квадратикам — обратные ребра; заштрихованные узлы указывают, что инцидентное ребро было обнаружено раньше, при поиске в другом направлении.

(рис 18.12) Другой лес DFS

Данный лес описывает поиск в глубину на том же графе, что и на рис 18.11, но здесь используется представление графа списками смежности, что меняет порядок поиска, поскольку он определяется порядком узлов в списках смежности. Вообще-то этот порядок виден из самого леса: это порядок, в каком перечислены потомки каждого узла дерева. Например, узлы списка смежности для вершины 0 расположены в порядке ), но вектор cc зависит только от свойств графа, поэтому он не изменился.

Особенности структуры конкретного леса позволяют понять, как ведет себя DFS на том или ином графе, но большая часть важных свойств DFS определяется свойствами графа, которые не зависят от структуры леса. Например, оба леса, показанные на рис 18.11 и рис 18.12, содержат по три дерева (как и любой другой лес DFS того же графа), поскольку это просто различные представления одного и того же графа, состоящего из трех связных компонентов. Ведь из доказательства того, что поиск в глубину посещает все узлы и ребра графа (см. леммы 18.2—18.4), следует, что число связных компонентов графа равно числу деревьев в лесе DFS. Этот пример демонстрирует основное применение поиска на графе в данной книге: огромное множество реализаций классов обработки графов основано на изучении свойств графа путем обработки конкретного его представления (леса, соответствующего поиску).

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

На рис 18.13 показано дерево DFS крупного графа, на котором видны базовые характеристики динамики поиска в глубину. Это высокое и узкое дерево демонстрирует несколько свойств просматриваемого графа и процесса поиска в глубину.

Существует как минимум один длинный путь, который соединяет существенную часть узлов.

Во время поиска у большинства вершин имеется по меньшей мере одна еще не просмотренная смежная вершина.

Из каждого узла редко выполняется более одного рекурсивного вызова.

Глубина рекурсии пропорциональна количеству вершин графа.

Такое поведение типично для поиска в глубину, хотя эти характеристики и не гарантируются для всех графов. Проверка подобных фактов для интересующих нас моделей графов и различных видов графов, возникающих на практике, требует тщательных исследований. Но все-таки этот пример позволяет почувствовать специфику алгоритмов на основе DFS, которая часто подтверждается на практике. рис 18.13 и аналогичные иллюстрации других алгоритмов поиска на графах (см. рис 18.24 и рис 18.29) помогают лучше понять различия в их поведении.

(рис 18.13) Поиск в глубину

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

Упражнения

18.15. Нарисуйте лес DFS, который получается при работе стандартного DFS на графе, заданном матрицей смежности:

3-71-47-80-55-23-82-90-64-92-66-4.

18.16. Нарисуйте лес DFS, который получается при работе стандартного DFS на графе, заданном списками смежности:

3-71-47-80-55-23-82-90-64-92-66-4.

18.17. Напишите программу трассировки поиска в глубину, которая в стиле рис 18.10 выводит характеристику каждого из двух представлений всех ребер графа: древесная ссылка, родительская ссылка, обратная ссылка или нисходящая ссылка в дереве DFS.

18.18. Напишите программу, которая вычисляет представление родительскими ссылками полного дерева DFS (включая внешние узлы) с помощью вектора из E целых чисел от 0 до V— 1. Указание. Первые V компонентов этого вектора должны совпадать с компонентами вектора st, описанного в тексте.

18.19. Добавьте в класс DFS остовного леса (программа 18.3) функции-члены (и соответствующие члены данных), которые возвращают высоту самого высокого дерева леса, количество обратных ребер и процент ребер, обработанных для просмотра всех вершин.

18.20. Определите эмпирически средние значения величин из упражнения 18.19 для графов различных размеров, построенных на основе различных моделей графов (см. упражнения 17.64—17.76).

18.21. Напишите функцию, выполняющую построение графа вставками в первоначально пустой граф ребер, выбранных случайным образом из заданного вектора. Используя эту функцию вместе с реализацией АТД графа списками смежности, определите эмпирически свойства распределения величин, описанных в упражнении 18.19, для всех представлений списками смежности различных крупных графов, построенных на основе различных моделей графов (см. упражнения 17.64—17.76).

Алгоритмы DFS

Независимо от структуры и представления графа, любой лес DFS позволяет нам определить, какие ребра являются древесными, а какие — обратными, и оценить структуру графа, а это позволяет строить на основе поиска в глубину решения многочисленных задач обработки графов. В мы уже ознакомились с основными примерами, связанными с поиском путей. В этом разделе мы рассмотрим реализации функций АТД на базе DFS, позволяющие решать эти и многие другие типовые задачи. В остальной части данной главы и в нескольких последующих лекциях мы рассмотрим различные решения гораздо более сложных задач.

Обнаружение циклов. Имеются ли в заданном графе циклы? (Является ли граф лесом?) Эта задача легко решается с помощью поиска в глубину, поскольку любое обратное ребро дерева DFS принадлежит циклу, состоящему из этого ребра и пути в дереве, соединяющего две вершины ребра (см. рис 18.9). Таким образом, поиск в глубину позволяет непосредственно выявлять циклы: граф является ациклическим тогда и только тогда, когда во время выполнения поиска в глубину не встречаются обратные ссылки (или нисходящие!). Например, для проверки этого условия в программе 18.1 достаточно добавить в оператор if предложение else, в котором проверяется равенство t и v. Если имеет место равенство, это означает, что обнаружена родительская ссылка w-v (второе представление ребра v-w, которое привело нас в w). Если равенства нет, то w-t замыкает цикл в дереве DFS, состоящий из ребер от t до w. Более того, нет необходимости проверять все ребра: мы должны либо найти цикл, либо завершить поиск, не обнаружив его, прежде чем проверим V ребер, ведь любой граф с V или большим числом ребер должен содержать цикл. Следовательно, мы можем проверить, является ли рассматриваемый граф ациклическим, за время, пропорциональное V, в случае представления списками смежности, хотя если граф задан в виде матрицы смежности, может понадобиться время, пропорциональное V² (чтобы найти ребра).

Простой путь. Существует ли путь в графе, который связывает две заданных вершины? В мы видели, что нетрудно построить класс DFS, который способен решить эту задачу за линейное время.

Простая связность. Как было сказано в разделе 18.3, алгоритм DFS позволяет за линейное время определить, является ли граф связным. Ведь выбранная нами стратегия основана на вызове функции поиска для каждого связного компонента. При проведении поиска в глубину граф является связным тогда и только тогда, когда функция поиска на графе вызывает рекурсивную функцию DFS только один раз (программа 18.2). Количество связных компонентов в графе равно как раз количеству вызовов рекурсивной функции из функции GRAPHsearch — значит, количество связных компонентов графа можно определить простым подсчетом таких вызовов.

Программа 18.4 содержит класс DFS для более общего случая. Он позволяет получать за постоянное время ответы на запросы, касающиеся связности, после этапа препроцес-сорной обработки в конструкторе, которая выполняется за линейное время. Порядок посещения вершин тот же, что и в программе 18.3. Рекурсивная функция в качестве второго аргумента принимает вершину, а не ребро, поскольку ей не нужно знать родительский узел. Каждому дереву леса DFS соответствует связный компонент графа, так что мы быстро можем определить, содержатся ли две вершины в одном и том же компоненте, включив в представление графа вектор, индексированный именами вершин, который заполняется при поиске в глубину и используется для ответов на запросы о связности. В рекурсивной функции DFS текущее значение счетчика компонентов присваивается элементу вектора, соответствующему каждой посещенной вершине. Тогда две вершины принадлежат одному компоненту графа тогда и только тогда, когда равны соответствующие им элементы этого вектора. Здесь данный вектор снова отображает структурные свойства графа, а не особенности представления графа или динамики поиска.

Программа 18.4. Связность графа

Конструктор CC вычисляет за линейное время количество связных компонентов заданного графа и сохраняет индекс компонента, которому принадлежит каждая вершина, в приватном векторе id, индексированном именами вершин. Клиенты могут использовать объект CC для определения за постоянное время количества связных компонентов (count) или для проверки (connect), является ли связанной какая-либо пара вершин.

  template <class Graph>
  class CC
    { const Graph G;
      int ccnt;
      vector <int> id;
      void ccR(int w)
        { id[w] = ccnt;
          typename Graph::adjIterator A(G, w);
          for (int v = A.beg(); !A.end(); v = A.nxt())
            if (id[v] == -1) ccR(v);
        }
    public:
      CC(const Graph G) : G(G), ccnt(0), id(G.V(), -1)
        { for (int v = 0; v < G.V(); v++)
          if (id[v] == -1) { ccR(v); ccnt+ + ; }
        }
      int count() const { return ccnt; }
      bool connect(int s, int t) const
        { return id[s] == id[t]; }
    };
      

Программа 18.4 типизирует базовый подход, который мы будем использовать при решении различных задач обработки графов. Мы разрабатываем класс, ориентированный на решение конкретной задачи, чтобы клиенты могли создавать объекты, решающие эту задачу. Как правило, мы затрачиваем некоторое время на предварительную обработку конструктором, который вычисляет приватные данные, описывающие нужные структурные свойства графа. Эти данные помогают обеспечить эффективную реализацию общедоступных функций для обработки запросов. В данном случае конструктор выполняет предварительную обработку с помощью поиска в глубину (за линейное время) и заполняет приватный член данных (вектор id, индексированный именами вершин), который позволяет отвечать на запросы о связности за постоянное время. В случаях других задач обработки графов конструкторы и функции обработки запросов могут затрачивать больше памяти и/или времени на предварительную обработку и на ответы на запросы. Как обычно, основное внимание мы уделяем минимизации этих затрат, хотя зачастую сделать это весьма непросто. Например, большая часть посвящена решению задачи связности для орграфов, для которых очень трудно добиться линейного времени на предварительную обработку и постоянного времени на обработку запросов о связности, как в программе 18.4.

Как соотносится определение связности графа на базе DFS, реализованное в программе 18.4, с алгоритмом объединения-поиска, который был рассмотрен в , если граф задан списком ребер? Теоретически поиск в глубину работает быстрее, поскольку он, в отличие от объединения-поиска, гарантирует постоянное время выполнения, однако на практике это редко играет роль. В конечном итоге, алгоритм объединения-поиска выполняется быстрее, поскольку в нем не обязательно строится полное представление графа. Что еще важнее, алгоритм объединения-поиска работает в оперативном режиме (в любой момент мы можем проверить, связаны ли какие-либо две вершины, за почти постоянное время), а решение на базе DFS должно выполнить предварительную обработку, чтобы ответить на запрос о связности за постоянное время. Поэтому мы, например, предпочитаем алгоритм объединения-поиска, если требуется определить связность графа лишь один раз или при наличии множества запросов, но вперемешку с операциями вставки ребер. Однако решение на базе DFS будет более подходящим для АТД графа, поскольку оно эффективно использует существующую инфраструктуру. Ни тот, ни другой подход не способен работать эффективно в случае смеси большого количества вставок ребер, удалений ребер и запросов определения связности; оба подхода требуют отдельных поисков в глубину для вычисления пути. Эти рассуждения показывают, с какими трудностями приходится сталкиваться при анализе алгоритмов на графах; подробнее мы рассмотрим их в разделе 18.9.

Двухсторонний эйлеров цикл. Программа 18.5 представляет собой класс для поиска пути с помощью поиска в глубину, который использует все ребра графа в точности два раза — по одному в каждом направлении (см. ). Этот путь соответствует методу Тремо: мы разматываем нить там, куда мы идем, проверяем, есть ли нить в коридоре, а не включаем свет (поэтому приходится проходить по коридорам, ведущим к уже пройденным перекресткам), и вначале проходим туда и сюда по каждой обратной ссылке (при первой встрече с обратным ребром), после чего игнорируем нисходящие ссылки (при второй встрече каждого обратного ребра). Можно также игнорировать обратные ссылки (при первой встрече) и проходить назад и вперед по нисходящим ссылкам (при второй встрече) (см. упражнение 18.25 и рис 18.14).

Программа 18.5. Двухсторонний эйлеров цикл

Этот класс DFS выводит каждое ребро дважды, по одному в каждом направлении, в порядке обхода двухстороннего эйлерова цикла. Мы проходим назад и вперед по обратным ребрам и игнорируем нисходящие ребра (см. текст). Этот класс порожден от базового класса SEARCH из программы 18.2.

  template <class Graph>
  class EULER : public SEARCH<Graph>
    { void searchC(Edge e)
        { int v = e.v, w = e.w;
          ord[w] = cnt+ + ;
          cout <<    << w;
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (ord[t] == -1)
              searchC(Edge(w, t));
            else if (ord[t] < ord[v])
              cout << "-" << t << "-" << w;
          if (v != w) cout << "-" << v; else cout << endl;
        }
    public:
      EULER(const Graph G) : SEARCH<Graph>(G)
        { search(); }
   };
      

(рис 18.14) Двухсторонний эйлеров цикл

Поиск в глубину позволяет исследовать любой лабиринт, проходя коридоры в обоих направлениях. Мы вносим изменения в метод Тремо: разматываем нить всюду, куда идем, и проходим туда и назад по коридорам, в которых нет нити и которые ведут к посещенным перекресткам. На этом рисунке показан порядок обхода, который отличается от изображенного на рисунках 18.2 и 18.3 — главным образом тем, что путь обхода можно нарисовать без пересечения себя. Такой порядок может быть, например, если при построении представления графа списками смежности ребра обрабатывались в каком-то другом порядке, либо при явном изменении алгоритма DFS, чтобы учесть геометрическое расположение узлов (см. упражнение 18.26). Двигаясь по нижнему пути из 0 через 2, 6, 4 и 7, мы пробуем пройти из 7 в 0 и возвращаемся назад,, поскольку ord[0] меньше ord[7]. Затем мы идем в 1, назад в 7, назад в 4, в 3, в 5, из 5 в 0 и назад, потом из 5 в 4 и назад, далее назад в 3, назад в 4, назад в 6, назад в 2 и назад в 0. Такой путь может быть получен с помощью прямого и обратного рекурсивного обхода дерева DFS (игнорируя заштрихованные вершины, которые означают вторую встречу с ребром), когда выводится имя соответствующей вершины, рекурсивно просматриваются поддеревья, затем снова выводится имя этой вершины.

Остовный лес. В заданном связном графе с V вершинами требуется найти множество из V— 1 ребер, соединяющих эти вершины. Если граф состоит из C связных компонентов, то нужно найти остовный лес (с V— C ребрами). Мы уже знаем класс DFS, который решает эту задачу — это программа 18.3.

Поиск вершин. Сколько вершин находится в том же компоненте, что и заданная вершина? Эту задачу можно легко решить, начав поиск в глубину с указанной вершины и подсчитывая количество помеченных вершин. В насыщенном графе этот процесс можно существенно ускорить, остановив поиск в глубину после пометки V вершин — в этот момент мы уже знаем, что никакое ребро не приведет нас в еще не помеченную вершину, поэтому остальные ребра можно игнорировать. Это усовершенствование позволит посетить все вершины за время, пропорциональное VlogV , а не E (см. раздел 18.8).

Раскраска двумя цветами, двудольные графы, нечетные циклы. Существует ли способ покрасить каждую вершину одним из двух цветов таким образом, чтобы ни одно из ребер не соединяло вершины одинакового цвета? Является ли данный граф двудольным (см. )? Содержит ли он цикл нечетной длины? Все эти три задачи эквивалентны: первые две — просто различные названия одной и той же задачи; любой граф, содержащий нечетный цикл, не допускает раскраску в два цвета, а программа 18.6 показывает, что любой граф, в котором нет нечетных циклов, может быть раскрашен двумя цветами. Эта программа представляет собой реализацию функции АТД на базе DFS, которая проверяет, является ли заданный граф двудольным, раскрашиваемым двумя цветами и не содержащим нечетные циклы. Эту рекурсивную функцию можно рассматривать как схему доказательства по индукции, что программа может раскрасить в два цвета любой граф без нечетных циклов (или обнаружить в графе нечетный цикл как доказательство того, что граф с нечетными циклами невозможно раскрасить двумя цветами). Чтобы раскрасить граф двумя цветами, нужно начать с раскраски вершины v одним цветом, а затем закрасить другим цветом все вершины, смежные с v. Этот процесс эквивалентен раскраске дерева DFS, спускаясь по уровням вниз и проверяя обратные ребра на соответствие цветов (см. рис 18.15). Любое обратное ребро, соединяющее вершины одного цвета, является свидетельством наличия в графе нечетного цикла.

Программа 18.6. Раскраска графа в два цвета (двудольность)

Конструктор этого DFS-класса заносит в DK значение true тогда и только тогда, когда может заполнить значениями 0 и 1 вектор vc, индексированный именами вершин, так, что для каждого ребра v-w графа значения vc[v] и vc[w] различны.

  template <class Graph>
  class BI
    { const Graph G;
      bool OK;
      vector <int> vc; 
      bool dfsR(int v, int c)
        { vc[v] = (c+1) % 2;
          typename Graph::adjIterator A(G, v);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (vc[t] == -1)
              { if (!dfsR(t, vc[v])) return false; }
            else if (vc[t] != c)
              return false;
          return true;
        }
    public:
      BI(const Graph G) : G(G), OK(true), vc(G.V(), -1)
        { for (int v = 0; v < G.V(); v++)
            if (vc[v] == -1)
              if (!dfsR(v, 0)) { OK = false; return; }
        }
      bool bipartite() const { return OK; }
      int color(int v) const { return vc[v]; }
    };
      

(рис 18.15) Раскраска дерева DFS двумя цветами

Чтобы раскрасить граф двумя цветами, мы меняем цвет при спуске по дереву DFS и проверяем обратные ребра на совместимость. В дереве DFS для графа с рис 18.9, изображенном в верхней части рисунка, обратные ребра (внизу), таких несоответствий нет; возможная раскраска показана штриховкой.

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

Упражнения

18.22. Реализуйте класс проверки наличия циклов на базе DFS, который выполняет в конструкторе предварительную обработку графа за время, пропорциональное V, и обеспечивает работу функций-членов, определяющих наличие в графе каких-либо циклов и выводящих найденные циклы.

18.23. Опишите семейство графов с V вершинами, в котором стандартный DFS по матрице смежности для обнаружения циклов выполняется за время, пропорциональное V².

18.24. Реализуйте класс определения связности из программы 18.4, производный от класса поиска на графе наподобие программы 18.3.

18.25. Опишите изменения, которые следует внести в программу 18.5, чтобы она могла вычислить двухсторонний эйлеров цикл, который выполняет проход туда и обратно по нисходящим, а не по обратным ребрам.

18.26. Измените программу 18.5, чтобы она вычисляла двусторонний эйлеров цикл, который можно нарисовать без пересечений себя ни в одной вершине (как на рис 18.14). Например, если бы поиск, представленный на рис 18.14, прошел сначала по ребру 4-3, а уже потом по ребру 4-7, то цикл пересек бы сам себя. Нужно, чтобы алгоритм не допускал таких пересечений.

18.27. Разработайте версию программы 18.5, которая сортирует все ребра в порядке двухстороннего эйлерова цикла. Программа должна возвратить вектор ребер, который соответствует двухстороннему эйлерову циклу.

18.28. Докажите, что граф можно раскрасить двумя цветами тогда и только тогда, когда он не содержит нечетных циклов. Указание. Докажите методом индукции, что программа 18.6 определяет, можно ли раскрасить двумя цветами любой заданный граф.

18.29. Объясните, почему подход, использованный в программе 18.6, не допускает обобщения до эффективного метода определения, можно ли раскрасить граф тремя цветами.

18.30. Большую часть графов невозможно раскрасить двумя цветами, и поиск в глубину обычно быстро обнаруживает это. Эмпирически определите количество ребер, просмотренных программой 18.6, для графов различных размеров и построенных по различным моделям (см. упражнения 17.64—17.76).

18.31. Докажите, что в каждом связном графе имеются вершины, удаление которых не нарушает связность графа, и напишите функцию DFS, которая обнаруживает такие вершины. Указание. Рассмотрите листья дерева DFS.

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

Разделимость и двусвязность

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

В некоторых ситуациях, когда важно, чтобы граф был связным, может оказаться существенным тот факт, что он остается связным, если убрать из него какую-либо вершину или ребро. То есть иногда нужно иметь более одного пути между каждой парой вершин графа с тем, чтобы застраховаться от возможных отказов. Например, из Нью-Йорка можно долететь в Сан-Франциско, даже если аэропорт в Чикаго завален снегом, т.к. имеется рейс через Денвер. Или возможна ситуация во время военных действий, когда желательно проложить такую железнодорожную сеть, что противнику для нарушения железнодорожного сообщения понадобится разрушить по меньшей мере две станции. Аналогично, было бы хорошо проложить соединения в интегральной схеме или в сети связи таким образом, что при обрыве какого-либо провода или отказе соединения остальная часть схемы продолжала работать.

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

Определение 18.1. Мостом (bridge) в графе называется ребро, после удаления которого связный граф распадается на два не связанных между собой подграфа. Граф, у которого нет мостов, называется реберно-связным (edge-connected).

Когда мы говорим об удалении ребра, мы имеем в виду удаление этого ребра из множества ребер, которое определяет граф, даже если после такого удаления одна или обе вершины этого ребра станут изолированными. Реберносвязный граф остается связным при удалении из него любого одного ребра. В некоторых контекстах естественнее говорить о разделении графа, а не о возможности графа оставаться связным. Поэтому мы будем свободно пользоваться альтернативной терминологией, которая делает акцент на таких моментах: граф, который не является реберно-связным, назовем реберно-разделимым (edge-separable), а мосты назовем ребрами разделения (separation edge).

(рис 18.16) Реберно-разделимый граф

Этот граф не является реберно-связным. Ребра 0-5, 6-7 и 11-12 (заштрихованы) представляют собой ребра разделения (мосты). Граф содержит четыре реберно-связных компонента: один включает вершины 0, 1, 2 и 6; другой — вершины 3, 4, 9 и 11; третий — вершины 7, 8 и 10; последний состоит из единственной вершины 12.

Если в реберно-разделимом графе удалить все мосты, он распадется на реберно-связные компоненты (edge-connected components) или компоненты, связанные мостами (bridge-connected components) — максимальные подграфы, не содержащие мостов. На рис 18.16 показан небольшой пример, иллюстрирующий эти понятия.

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

Лемма 18.5. В любом дереве DFS древесное ребро v-w является мостом тогда и только тогда, когда не существуют обратные ребра, соединяющие одного из потомков w с предком w.

Доказательство. Если такое ребро существует, то v-w не может быть мостом. С другой стороны, если v-w не есть мост, то в графе должен быть другой путь из w в v, отличный от w-v. Каждый такой путь должен содержать одно из таких ребер. $$$\blacksquare$$$

Эта лемма эквивалентна утверждению, что единственная ссылка поддерева с корнем в w, указывающая на узел, который не входит в это поддерево — это родительская ссылка из w назад в v. Это условие соблюдается тогда и только тогда, когда каждый путь, соединяющий любой узел в поддереве узла w, с любым узлом, не принадлежащим этому поддереву, содержит ребро v-w. Другими словами, удаление ребра v-w отделяет подграф, соответствующий поддереву узла w, от остальной части графа.

Программа 18.7 показывает, как можно изменить поиск в глубину, чтобы он мог выявлять мосты в графах с помощью программы 18.5. Для каждой вершины v рекурсивная функция вычисляет минимальный прямой номер, до которого можно дойти через последовательность из нуля или более ребер дерева с последующим единственным обратным ребром из любого узла поддерева с корнем в вершине v. Если вычисленный номер равен прямому номеру вершины v, то не существует ребра, связывающего потомка вершины v с ее предком — то есть найден мост.

(рис 18.17) Дерево DFS для поиска мостов

Здесь приведено дерево DFS для графа с рис 18.16. Узлы 5, 7 и 12 обладают тем свойством, что никакое обратное ребро не соединяет потомка с предком, и этим свойством не обладают никакие другие узлы. Поэтому удаление ребра между одним из этих узлов и его родительским узлом отделит поддерево с корнем в этом узле от остальной части графа. То есть ребра 0-5, 11-12 и 6-7 являются мостами. Массив low, индексированный именами вершин, используется для отслеживания минимального прямого номера (значение ord), на который указывает любое обратное ребро в поддереве, корнем которого является эта вершина. Например, low[9] содержит значение 2, т.к. одно из обратных ребер в поддереве с корнем в 9 указывает на 4 (вершина с прямым номером 2), и никакое другое обратное ребро не указывает на более высокую вершину в этом дереве. Для узлов 5, 7 и 12 значение low равно значению ord.

Программа 18.7. Реберная связность

Этот класс DFS подсчитывает количество мостов в графе. Клиент может использовать объект EC для определения количества реберно-связных компонентов. Добавление функции-члена, проверяющей, содержатся ли какие-либо две вершины в одном и том же реберно-связном компоненте, предлагается как самостоятельное упражнение (см. упражнение 18.36). Вектор low содержит минимальные прямые номера, которые могут быть достигнуты из каждой вершины через некоторую последовательность древесных ребер, за которой следует одно обратное ребро.

  template <class Graph>
  class EC : public SEARCH<Graph>
    { int bcnt;
      vector <int> low;
      void searchC(Edge e)
        { int w = e.w;
          ord[w] = cnt+ + ; low[w] = ord[w];
          typename Graph::adjIterator A(G, w);
          for (int t = A.beg(); !A.end(); t = A.nxt())
            if (ord[t] == -1)
              { searchC(Edge(w, t));
                if (low[w] > low[t]) low[w] = low[t];
                if (low[t] == ord[t])
                  bcnt++; // w-t является мостом
              }
            else if (t != e.v)
              if (low[w] > ord[t]) low[w] = ord[t];
        }
    public:
      EC(const Graph G) : SEARCH<Graph>(G),
        bcnt(0), low(G.V(), -1)
          { search(); }
      int count() const { return bcnt+1; }
    };
      

Вычисления для каждой вершины достаточно просты: мы просматриваем список смежности, отслеживая минимальные номера, которых можно достичь, проходя по каждому ребру. Для древесных ребер вычисления выполняются рекурсивно; для обратных ребер используется прямой номер смежной вершины. Если вызов рекурсивной функции для ребра w-t не находит путь к узлу с меньшим прямым номером, чем прямой номер узла t, то ребро w-t является мостом.

Лемма 18.6. Мосты графа можно найти за линейное время

Доказательство. Программа 18.7 представляет собой разновидность поиска в глубину с несколькими дополнительными проверками, которые выполняются за постоянное время. Поэтому из лемм 18.3 и 18.4 непосредственно следует, что поиск мостов в графе выполняется за время, пропорциональное V² для представления матрицей смежности и V + E для представления списками смежности. $$$\blacksquare$$$

В программе 18.7 для исследования свойств графа используется поиск в глубину. Разумеется, представление графа влияет на порядок поиска, но оно никак не влияет на результаты, т.к. мосты — характеристика графа, а не способа его представления или поиска на нем. Как всегда, любое дерево DFS — это просто еще одно представление графа, поэтому все такие деревья обладают одними и теми же свойствами связности. Корректность алгоритма зависит от этого фундаментального факта. Например, на рис 18.18 показан другой поиск на том же графе; он начинается с другой вершины, но, естественно, обнаруживает те же самые мосты. Несмотря на лемму 18.6, при исследовании различных деревьев DFS одного и того же графа стоимость поиска может зависеть не только от свойств графа, но и от свойств дерева DFS. Например, объем памяти, необходимой для стека, который обеспечивает поддержку рекурсивных вызовов, больше для примера на рис 18.18, чем для примера на рис. 18.17 рис 18.17.

(рис 18.18) Другое дерево DFS, используемое для поиска мостов

На этой диаграмме показано дерево DFS для графа с рис 18.16, которое отлично от дерева, изображенного на рис 18.17 — там поиск начинается с другого узла. Узлы и ребра просматриваются в совершенно другом порядке, но мосты находятся (естественно) одни и те же. В этом дереве вершины 0, 7 и 11 — это вершины, для которых значение low равно значению ord, поэтому ребра, соединяющие каждую из этих вершин с их родителями (соответственно, 12-11, 5-0 и 6-7) являются мостами.

Как и в случае обычной связности в программе 18.4, можно воспользоваться программой 18.7 для построения класса, который сможет проверить, является ли заданный граф реберно-связным, либо подсчитать количество реберно-связных компонентов. При желании, как и для программы 18.4, можно предоставить клиентам возможность создавать (за линейное время) объекты, способные за постоянное время отвечать на запросы, находятся ли две заданные вершины в одном и том же реберно-связном компоненте (см. упражнение 18.36).

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

(рис 18.19) Терминология разделимости графа

Этот граф состоит из двух реберно-связных компонентов и одного моста. К тому же реберно-связный компонент, расположенный над мостом, является двусвязным, а компонент ниже моста состоит из двух двусвязных компонентов, соединенных точкой сочленения.

Когда речь идет об удалении вершины, то при этом подразумевается и удаление всех инцидентных ей ребер. Как показано на рис 18.19, при удалении любой из вершин моста нарушается связность графа (если, конечно, этот мост не был единственным ребром, инцидентным одной или обеим вершинам), но это свойство присуще и другим вершинам, не связанным с мостами.

Определение 18.2. Точка сочленения (articulation point) графа — это вершина, при удалении которой связный граф распадается по меньшей мере на два непересекаю-щихся подграфа.

Точки сочленения графа мы будем также называть вершинами разделения (separation vertex) или разрезающими вершинами (cut vertex). Граф, в котором нет вершин разделения, можно было бы назвать " вершинно-связным " , но мы воспользуемся другой, хотя в конечном счете и эквивалентной, терминологией.

Определение 18.3. Граф называется двусвязным (biconnected), если каждая пара его вершин соединена двумя непересекающимися путями.

Требование непересекающихся (disjoint) путей отличает двусвязность от реберной связности. Другое определение реберной связности — когда каждая пара вершин связана двумя путями без общих ребер, хотя эти пути могут иметь общие вершины. Двусвязность представляет собой более сильное условие: реберно-связный граф остается связным при удалении любого ребра, а двусвязный граф остается связным при удалении любой вершины (и всех инцидентных ей ребер). Каждый двусвязный граф является реберносвязным, однако реберно-связный граф не обязательно должен быть двусвязным. Граф, который не является двусвязным, иногда называется разделимым (separable), поскольку его можно разделить на две части, удалив лишь одну вершину. Ключом к двусвязности являются вершины разделения.

Лемма 18.7. Граф двусвязен тогда и только тогда, когда он не содержит вершин разделения (точек сочленения).

Доказательство. Предположим, что в графе имеется вершина разделения. Пусть s и t — две вершины, которые окажутся в двух различных частях графа после удаления этой вершины. Все пути, связывающие s и t, должны проходить через вершину разделения, поэтому граф не может быть двусвязным. Доказательство в обратном направлении несколько труднее и предлагается в качестве упражнения математически подготовленным читателям (см. упражнение 18.40). $$$\blacksquare$$$

(рис 18.20) Точки сочленения (вершины разделения)

Данный граф не является двусвязным. Вершины 0, 4, 5, 6, 7 и 11 (обведены) — точки сочленения. Граф содержит пять двусвязных компонентов: один состоит из ребер 4-9, 9-11 и 4-11, другой — из ребер 7-8, 8-10 и 7-10; еще один — из ребер 0-1, 1-2, 2-6 и 6-0; следующий — из ребер 3-5 , 4-5 и 3-4; и еще имеется одиночная вершина 12. Добавление в граф ребра, соединяющего вершину 12 с вершиной 7, 8 или 10, делает граф двусвязным.

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

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

Для определения двусвязности графа и выявления точек сочленения можно использовать тот же подход на основе DFS, что и в программе 18.7. Мы не будем рассматривать соответствующий код, поскольку он почти идентичен программе 18.7, за исключением дополнительной проверки, является ли корень дерева DFS точкой сочленения (см. упражнение 18.43). Хорошим упражнением может послужить разработка кода вывода двусвязных компонентов графа, который лишь ненамного сложнее, чем соответствующий код определения реберной связности графа (см. упражнение 18.44).

Лемма 18.8. Точки сочленения и двусвязные компоненты графа можно найти за линейное время.

Доказательство. Как и в случае леммы 18.7, этот факт непосредственно следует из того, что решения упражнений 18.43 и 18.44 добавляют в поиск в глубину лишь небольшие изменения — несколько проверок для каждого ребра, выполняемых за постоянное время. $$$\blacksquare$$$

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

Определение 18.4. Граф называется k-связным (k-connected), если каждую пару его вершин соединяют по меньшей мере k путей без общих вершин. Вершинная связность (vertex connectivity) графа — это минимальное количество вершин, которые нужно удалить, чтобы разделить этот граф на две части.

В этой терминологии " 1-связный " означает просто " связный " , а " 2-связный " — это то же, что и " двусвязный " . Граф с точкой сочленения обладает вершинной связностью, равной 1 (или 0), поэтому из леммы 18.7 следует, что граф 2-связен тогда и только тогда, когда значение его вершинной связности не меньше 2. Это частный случай классического результата теории графов — теоремы Уитни (Whitney’s theorem), которая гласит, что граф k-связен в том и только том случае, когда его вершинная связность не меньше k. Теорема Уитни непосредственно следует из теоремы Менгера (Menger’s theorem) (см. ), согласно которой минимальное количество вершин, удаление которых разъединяет две вершины в графе, равно максимальному количеству путей без общих вершин между этими двумя вершинами (для доказательства теоремы Уитни нужно применить теорему Менгера к каждой паре вершин).

Определение 18.5. Граф называется k-реберно-связным (k-edge-connected), если существуют по меньшей мере k путей без общих ребер, соединяющих каждую пару вершин графа. Реберная связность (edge connectivity) графа — это минимальное число ребер, которые нужно удалить, чтобы разделить этот граф на две части.

В этой терминологии " 2-реберно-связный " означает просто " реберно-связный " (т.е. для реберно-связного графа значение реберной связности должно быть больше 1). Другой вариант теоремы Менгера утверждает, что минимальное количество вершин в графе, удаление которых приводит к разъединению двух вершин графа, равно максимальному количеству путей без общих вершин, связывающих эти две вершины графа. Отсюда следует, что граф k-реберно-связен тогда и только тогда, когда его реберная связность равна k.

Эти определения приводят нас к обобщению задач определения связности, которые рассматривались в начале данного раздела.

st-связность. Каково минимальное количество ребер, удаление которых приведет к разъединению двух вершин s и t заданного графа? Каково минимальное количество вершин, удаление которых приведет к разъединению двух вершин s и t заданного графа?

Общая связность. Является ли заданный граф k-связным? Является ли заданный граф k-реберно-связным? Чему равны реберная связность и вершинная связность заданного графа?

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

Упражнения

18.33. Если граф является лесом, все его ребра являются ребрами разделения. А какие вершины являются вершинами разделения?

18.34. Рассмотрим граф

3-71-47-80-55-23-82-90-64-92-66-4.

Начертите стандартное дерево DFS для списков смежности. Найдите с его помощью мосты и реберно-связные компоненты.

18.35. Докажите, что каждая вершина любого графа принадлежит в точности одному реберно-связному компоненту.

18.36. Добавьте в программу 18.7 общедоступную функцию-член, которая позволит клиентам проверять, принадлежит ли пара заданных вершин одному и тому же реберно-связному компоненту.

18.37. Рассмотрим граф

3-71-47-80-55-23-82-90-64-92-66-4.

Начертите стандартное дерево DFS для списков смежности. Найдите с его помощью точки сочленения и двусвязные компоненты.

18.38. Выполните предыдущее упражнение, воспользовавшись стандартным деревом DFS для матрицы смежности.

18.39. Докажите, что каждое ребро графа либо является мостом, либо принадлежит в точности одному двусвязному компоненту.

18.40. Докажите, что любой граф без точек сочленения является двусвязным. Указание. Если заданы пара вершин s и t и соединяющий их путь, воспользуйтесь тем фактом, что ни одна из вершин этого пути не является точкой сочленения для построения двух непересекающихся путей, которые соединяют вершины s и t.

18.41. Напишите производный от программы 18.2 класс для определения, является ли граф двусвязным. Воспользуйтесь примитивным алгоритмом, который выполняется за время, пропорциональное V(V + E). Указание: Если перед началом поиска какая-то вершина отмечена как уже просмотренная, то это по сути удаляет ее из графа.

18.42. На основе решения упражнения 18.41 постройте класс, который определяет, является ли заданный граф 3-связным. Выведите формулу для приближенного количества просмотров каждого ребра графа в виде функции от V и E.

18.43. Докажите, что корень дерева DFS является точкой сочленения тогда и только тогда, когда у него имеется два или более (внутренних) дочерних узлов.

18.44. Пользуясь программой 18.2, напишите производный класс, который выводит двусвязные компоненты графа.

18.45. Чему равно минимальное количество ребер в любом двусвязном графе с V вершинами?

18.46. Измените программу 18.7, чтобы упростить задачу определения, является ли заданный граф реберно-связным (которая завершает работу сразу при обнаружении моста, если граф не реберно-связный), и добавьте возможность отслеживать количество просмотренных ребер. Эмпирически определите затраты для графов различных размеров, сгенерированных на основе различных моделей графов (упражнения 17.64-17.76).

18.47. Пользуясь программой 18.2, напишите производный класс, позволяющий клиентам создавать объекты, которым известны количества точек сочленения, мостов и двусвязных компонентов графа.

18.48. Эмпирически определите средние значения величин, описанных в упражнении 18.47, для графов различных размеров, сгенерированных на основе различных моделей графов (упражнения 17.64—17.76).

18.49. Определите реберную связность и вершинную связность графа

0-10-20-82-12-88-13-83-73-63-53-44-64-55-66-77-8.

Поиск в ширину

Предположим, что нам нужно найти кратчайший путь между двумя конкретными вершинами графа — такой путь, соединяющий эти вершины, что никакой другой путь между этими вершинами не содержит меньшее число ребер. Классический метод решения этой задачи, получивший название поиска в ширину (BFS — breadth-first search), также лежит в основе многочисленных алгоритмов обработки графов; ему и посвящен данный раздел. Поиск в глубину мало пригоден для решения этой задачи, поскольку порядок прохождения им графа никак не связан с поиском кратчайших путей. А вот поиск в ширину очень удобен для этого. Поиск кратчайшего пути от вершины v к вершине w мы начнем с того, что попытаемся найти вершину w среди всех вершин, в которые можно перейти по одному ребру из вершины v, затем проверим все вершины, в которые можно перейти по двум ребрам и т.д.

Когда во время просмотра графа мы попадаем в вершину, из которой исходят более одного ребра, мы выбираем одно из них и запоминаем остальные для последующего просмотра. В поиске в глубину для этой цели применяется стек магазинного типа (которым управляет система при вызовах рекурсивной функции поиска). Применение правила LIFO (Last In First Out — последним пришел, первым вышел), которое характеризует работу стека магазинного типа, соответствует исследованию соседних коридоров в лабиринте: из всех еще не исследованных коридоров выбирается последний обнаруженный. В поиске в ширину необходимо исследовать вершины в порядке их удаления от исходной точки. В случае реального лабиринта для такого исследования может потребоваться целая бригада; однако в компьютерной программе эта цель достигается намного проще: вместо стека используется очередь FIFO (First In First Out — первым пришел, первым вышел).

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

Выбираем ребра из очереди до тех пор, пока не найдем такое ребро, которое указывает на непосещенную вершину.

Посещаем эту вершину; заносим в очередь все ребра, исходящие из этой вершины в еще не посещенные вершины.

На рис 18.21 показано выполнение поиска в ширину на конкретном примере.

(рис 18.21) Поиск в ширину

Здесь показаны шаги поиска в ширину на примере графа. Мы начинаем его со всех ребер, смежных с находящейся в очереди исходной вершиной (вверху слева). Потом мы переносим ребро 0-2 из очереди в дерево и обрабатываем инцидентные ему ребра 2-0 и 2-6 (вторая диаграмма сверху слева). Мы не помещаем ребро 2-0 в очередь, поскольку вершина 0 уже содержится в дереве.

Затем мы переносим из очереди в дерево ребро 0-5; одно из ребер, инцидентных вершине 5, также не приводит в новую вершину, однако мы добавляем в очередь ребра 5-3 и 5-4 (третья диаграмма сверху слева). После этого мы добавляем в дерево ребро 0-7 и заносим в очередь ребро 7-1 (внизу слева).

Ребро 7-4 не выделено серым цветом: его можно не заносить в очередь, т.к. другое ребро уже привело нас в вершину 4, и она уже помещена в очередь. Для завершения поиска мы удаляем оставшиеся ребра из очереди, полностью игнорируя при этом серые ребра, когда они подходят к началу очереди (справа). Ребра заносятся в очередь и выбираются из нее в порядке их удаленности от вершины 0.

Программа 18.8. Поиск в ширину

Данный класс поиска на графе при посещении вершины просматривает все инцидентные ей ребра и помещает ребра, ведущие в непосещенные вершины, в очередь вершин, ожидающих посещения. Маркировка вершин в порядке их посещения хранится в векторе ord. Функция search, вызываемая конструктором, строит явное представление дерева BFS родительскими ссылками (ребра, которые впервые приводят нас в каждый узел) в другом векторе st, который затем можно использовать для решения базовой задачи поиска кратчайшего пути (см. текст).

  #include "QUEUE.cc"
  template <class Graph>
  class BFS : public SEARCH<Graph>
    { vector<int> st;
      void searchC(Edge e)
        { QUEUE<Edge> Q;
          Q.put(e);
          while (!Q.empty())
            if (ord[(e = Q.get()).w] == -1)
              { int v = e.v, w = e.w;
                ord[w] = cnt++; st[w] = v;
                typename Graph::adjIterator A(G, w);
                for (int t = A.beg(); !A.end(); t = A.nxt())
                  if (ord[t] == -1) Q.put(Edge(w, t));
              }
        }
    public:
      BFS(Graph G) : SEARCH<Graph>(G), st(G.V(), -1)
        { search(); } 
      int ST(int v) const { return st[v]; }
   };
      

Как было показано в разделе 18.4, поиск в глубину подобен исследованию лабиринта одним человеком. Поиск в ширину можно сравнить с исследованием группой людей, которые расходятся веером по всем направлениям. Методы DFS и BFS отличаются друг от друга во многих отношениях, но между этими двумя методами существует глубинная связь — о ней было сказано в кратком анализе методов в . В разделе 18.8 мы рассмотрим обобщенный метод поиска на графе, который можно настроить так, чтобы он включал в себя и оба эти алгоритма, и множество других. Каждый алгоритм обладает особыми динамическими характеристиками, которые мы используем для решения соответствующих задач обработки графов. В случае поиска в ширину нас наиболее интересует расстояние каждой вершины от исходной вершины (длина соединяющего их кратчайшего пути).

Лемма 18.9. В процессе поиска в ширину вершины заносятся в очередь FIFO и выбираются из нее в порядке их расстояния от исходной вершины.

Доказательство. Справедливо более сильное условие: очередь всегда содержит ноль или более вершин, удаленных на расстояние k от исходной вершины, за которой следует ноль или более вершин, удаленных на расстояние k + 1 от исходной точки, где k — некоторое целое значение. Это более сильное условие легко доказывается методом индукции. $$$\blacksquare$$$

В случае поиска в глубину мы выявляли динамические характеристики этого алгоритма с помощью леса поиска DFS, который описывает структуру рекурсивных вызовов алгоритма. Основное свойство этого леса состоит в том, что он представляет пути из каждой вершины в точку, откуда начался поиск содержащего ее связного компонента. Как видно из реализации и рис.18.22, такое остовное дерево помогает также понять суть поиска в ширину. Как и в случае DFS, мы имеем лес, описывающий динамику поиска: деревья соответствуют связным компонентам, узлы — вершинам графа, а ребра дерева — ребрам графа. Поиск в ширину соответствует обходу каждого дерева этого леса по уровням. Как и в случае DFS, для явного представления леса родительскими ссылками используется вектор, индексированный именами вершин. Этот лес содержит важную информацию о структуре графа:

Лемма 18.10. Для любого узла w в дереве BFS с корнем в вершине v путь из v в w соответствует кратчайшему пути из v в w в соответствующем графе.

Доказательство. Длины путей в дереве из узлов, извлекаемых из очереди, в корень дерева представляют собой неубывающую последовательность, и все узлы, расположенные ближе к корню, чем w, находятся в очереди. Следовательно, невозможно найти более короткий путь до w до ее извлечения из очереди, и никакие пути в w после ее извлечения из очереди не могут быть короче, чем длина пути в дереве в вершину w. $$$\blacksquare$$$

Как показано на , нет необходимости помещать в очередь ребро с такой же конечной вершиной, что и у хотя бы одного ребра, которое уже находится в очереди, поскольку правило FIFO гарантирует обработку ребра, которое уже находится в очереди (и посещение соответствующей вершины), раньше, чем алгоритм доберется до нового ребра. Один из способов реализации этого правила заключается в использовании реализации АТД очереди, в которой одинаковые элементы запрещены принципом игнорирования новых элементов (см. ). Другой способ — применение для этой цели глобального вектора пометки вершин: вместо пометки вершины в момент ее извлечения из очереди как посещенной, это делается при занесении ее в очередь. Проверка, помечена ли вершина (изменилось ли значение соответствующего элемента с начального сигнального значения), как раз и запрещает включение в очередь других ребер, которые указывают на эту вершину. Это изменение, показанное в программе 18.9, позволяет получить реализацию поиска в ширину, в очереди которой не бывает более V ребер (в каждую вершину ведет не более одного ребра).

(рис 18.22) Дерево BFS

Это дерево представляет собой компактное описание динамических характеристик поиска в глубину, аналогично дереву, которое показано на рис 18.9. Обход дерева по уровням показывает, как выполняется поиск: сначала мы посещаем вершину 0, потом вершины 2, 5 и 7, затем, находясь в 2, мы выясняем, что в вершине 0 мы уже были, и направляемся в 6 и т.д. У каждого узла дерева имеются дочерние узлы, которые представляют узлы, смежные с этим узлом, в том порядке, в каком они рассматриваются алгоритмом BFS. Как и на рис 18.9, ссылки дерева BFS соответствуют ребрам графа: если заменить ребра, ведущие во внешние узлы, на линии, ведущие в заданный узел, то мы получим чертеж графа. Ссылки, ведущие во внешние узлы, представляют собой ребра, которые не были помещены в очередь, потому что они ведут в помеченные узлы: это либо родительские ссылки, либо перекрестные ссылки, которые указывают на узел, находящийся на том же уровне или на уровне, более близком к корню дерева.

Вектор st являетсяпредставлени-ем дерева родительскими ссылками, которое можно использовать для поиска кратчайшего пути из любого узла в корень. Например, 3-5-0 — путь в графе из 3 в 0, поскольку st[3] равно 5, а st[5] равно 0. Более короткого пути из 3 в 0 не существует.

Лемма 18.11. Поиск в ширину посещает все вершины и ребра графа за время, пропорциональное V², для представления матрицей смежности и за время, пропорциональное V + E, для представления списками смежности.

Доказательство. Так же, как при доказательстве аналогичных свойств DFS, анализ кода показывает, что каждый элемент строки матрицы смежности или списка смежности проверяется в точности один раз для каждой посещаемой вершины — следовательно, достаточно показать, что BFS посещает каждую вершину. Для каждого связного компонента алгоритм сохраняет следующий инвариант: все вершины, в которые можно попасть из исходной вершины, (1) включены в дерево BFS, (2) занесены в очередь или (3) достижимы из одной из вершин, занесенных в очередь. Каждая вершина перемещается из (3) в (2) и в (1), а количество вершин в (1) увеличивается при каждой итерации цикла; значит, в конечном итоге дерево BFS будет содержать все вершины, достижимые из исходной вершины. Это дает, как и в случае DFS, основание утверждать, что алгоритм BFS выполняется за линейное время. $$$\blacksquare$$$

Программа 18.9. Усовершенствованный BFS

Чтобы очередь, используемая при выполнении BFS, содержала не более V элементов, мы помечаем вершины в момент занесения их в очередь.

  void searchC(Edge e)
    { QUEUE<Edge> Q;
      Q.put(e); ord[e.w] = cnt++;
      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.4, поскольку рассмотренные решения зависят только от способности алгоритма поиска просмотреть все узлы и все ребра, связанные с исходной точкой. Как мы увидим, алгоритмы BFS и DFS лежат в основе многочисленных алгоритмов, обладающих этим свойством. Как было сказано в начале данного раздела, алгоритм BFS интересует нас в основном потому, что он является естественным алгоритмом поиска на графе, когда требуется найти кратчайший путь между двумя заданными вершинами. Теперь мы рассмотрим конкретное решение этой задачи и его расширение для решения двух других сходных задач.

Кратчайший путь. Нужно найти кратчайший путь на графе из v в w. Эту задачу можно выполнить, запустив процесс поиска в ширину, который создает в векторе st представление родительскими ссылками дерева поиска из v и останавливается по достижении вершины w. Путь вверх по дереву из w в v и является кратчайшим. Например, после построения экземпляра bfs класса BFS<Graph> клиент может использовать следующий код для вывода пути из w в v:

  for (t = w; t != w; t = bfs.ST(t)) cout << t << "-";
  cout << v << endl;
      

Чтобы получить путь из v в w, нужно заменить в этом коде операции cout операциями занесения в стек и добавить цикл, который выводит индексы этих вершин после выталкивания их из стека. Либо можно запустить поиск из w и остановить его по достижении v.

Кратчайшие пути из одного источника. Нужно найти кратчайшие пути, соединяющие заданную вершину v со всеми другими вершинами графа. Эту задачу позволяет решить полное дерево BFS с корнем в вершине v: путь из каждой вершины в корень является кратчайшим путем в корень. Поэтому для решения этой задачи необходимо выполнить поиск в ширину из вершины v до полного завершения. Полученный при этом вектор st является представлением дерева BFS родительскими ссылками, а код из предыдущего абзаца позволяет получить кратчайший путь в любую другую вершину w.

Кратчайшие пути для всех пар вершин. Нужно найти кратчайшие пути, соединяющие каждую пару вершин графа. Эту задачу можно выполнить с помощью класса BFS, который решает задачу с одним источником для каждой вершины графа и использует функции-члены, которые могут эффективно обрабатывать большое количество запросов на определение кратчайших путей, сохраняя длины путей и представления деревьев родительскими ссылками для каждой вершины (см. рис 18.23). Такая предварительная обработка требует времени, пропорционального VE, и объема памяти, пропорционального V², что делает невозможной обработку больших разреженных графов. Однако она позволяет строить АТД с оптимальной производительностью: после затраты времени на предварительную обработку (и памяти для сохранения результатов этой обработки) можно вычислять длины кратчайших путей за постоянное время, а сами пути — за время, пропорциональное их длине (см. упражнение 18.55).

Такие решения на основе BFS вполне эффективны, однако здесь мы не будем рассматривать конкретные реализации, поскольку они представляют собой специальные случаи алгоритмов, которые будут подробно рассмотрены в . Термин кратчайший путь в отношении графов обычно используется для описания соответствующих задач в орграфах и сетях. Этой теме посвящена . Приведенные там решения являются строгими обобщениями описанных здесь решений на базе BFS.

Базовые характеристики динамики поиска существенно отличаются от аналогичных характеристик поиска в глубину — см. пример для большого графа на рис 18.24 и сравните его с рис 18.13. Дерево имеет небольшую глубину, зато большую ширину. Оно демонстрирует множество отличий поиска в ширину на графе от поиска в глубину. Например:

Существует относительно короткий путь, соединяющий каждую пару вершин графа.

Во время поиска большая часть вершин смежна с многими непосещенными вершинами.

Опять-таки, этот пример типичен для поведения, которое мы ожидаем от поиска в ширину, однако следует тщательно проверять подобные факты для интересующих нас моделей графов и графов, с которыми приходится сталкиваться на практике.

(рис 18.23) Пример определения кратчайших путей для всех пар вершин

Эти диаграммы описывают результат выполнения поиска в ширину из каждой вершины, т.е. вычисления кратчайших путей, соединяющих все пары вершин. Каждый поиск приводит к построению дерева BFS, которое определяет кратчайшие пути, соединяющие все вершины графа с вершиной в корне дерева. Результаты всех поисков сводятся в две матрицы, показанные в нижней части рисунка.

В левой матрице элемент на пересечении строки v и столбца w содержит длину кратчайшего пути из v в w (глубину v в дереве w). Каждая строка правой матрицы содержит массив st для соответствующего поиска. Например, кратчайший путь из 3 в 2 состоит из трех ребер, как показывает элемент левой матрицы, расположенный на пересечении строки 3 и столбца 2. Третье сверху слева дерево BFS говорит, что это путь 3-4-6-2 — данная информация закодирована в строке 2 правой матрицы. При наличии нескольких кратчайших путей матрица не обязательно должна быть симметричной, поскольку найденные пути зависят от порядка выполнения поиска в ширину. Например, дерево BFS, показанное внизу слева, и строка 3 правой матрицы говорят, что кратчайшим путем из 2 в 3 является 2-0-5-3.

(рис 18.24) Поиск в ширину

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

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

Главное для понимания алгоритмов обработки графов — уяснить не только то, что существуют различные стратегии поиска как эффективное средство изучения различных свойств графов, но и то, что многие из них можно реализовать стандартным путем. Например, поиск в глубину, показанный на рис 18.13, обнаруживает, что в графе имеется длинный путь, а поиск в ширину, изображенный на рис 18.24, говорит о том, что в графе присутствуют многочисленные короткие пути. Но, несмотря на упомянутые различия в динамике, алгоритмы DFS и BFS имеют много общего. Они существенно различаются лишь структурой данных, которая используется для хранения еще не исследованных ребер (и случайной возможностью использовать рекурсивную реализацию DFS с системной поддержкой неявного стека). Теперь мы обратимся к обобщенным алгоритмам поиска на графах, которые охватывают как DFS и BFS, так и множество других полезных стратегий, и могут служить основой для решения разнообразных классических задач обработки графов.

Упражнения

18.50. Начертите лес BFS, построенный стандартным BFS по спискам смежности для графа

3-71-47-80-55-23-82-90-64-92-66-4.

18.51. Начертите лес BFS, построенный стандартным BFS по матрице смежности для графа

3-71-47-80-55-23-82-90-64-92-66-4.

18.52. Измените программы 18.8 и 19.9, чтобы использовать в них контейнер queue из библиотеки STL вместо АТД из .

18.53. Приведите реализацию BFS (на основе программы 18.9), которая использует очереди вершин (см. программу 5.22). Включите в нее проверку, не допускающую занесения в очередь одинаковых вершин.

18.54. Приведите матрицы всех кратчайших путей (в стиле рис 18.23) для графа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4,

представленного матрицей смежности.

18.55. Разработайте класс поиска кратчайших путей, который после предварительной обработки отвечает на запросы о кратчайших путях. А именно, определите двухмерную матрицу как приватный член данных и напишите конструктор, который присваивает значения всем ее элементам, как показано на рис 18.23. Затем напишите две функции запросов: функцию length(v, w), которая возвращает длину кратчайшего пути между вершинами v и w, и функцию path(v, w), которая возвращает вершину, смежную с v на кратчайшем пути между v и w.

18.56. Что можно узнать из дерева BFS о расстоянии между вершинами v от w, когда ни одна из них не является корнем этого дерева?

18.57. Разработайте класс, объектам которого известна длина пути, достаточного для соединения любой пары вершин конкретного графа. (Эта величина называется диаметром графа). Примечание: Необходимо сформулировать соглашение, какое значение возвращать, если граф окажется несвязным.

18.58. Приведите простой и оптимальный рекурсивный алгоритм вычисления диаметра дерева (см. упражнение 18.57).

18.59. Добавьте в класс BFS из программы 18.9 функции-члены (и соответствующие приватные члены данных), возвращающие высоту дерева BFS и процент ребер, которые необходимо обработать, чтобы добраться до каждой вершины.

18.60. Эмпирически определите средние значения величин, описанных в упражнении 18.59, для графов различных размеров и построенных на основе различных моделей (упражнения 17.64—17.76).

Обобщенный поиск на графах

Алгоритмы DFS и BFS — фундаментальные и важные методы, лежащие в основе многочисленных алгоритмов обработки графов. Зная их основные свойства, мы можем перейти на более высокий уровень абстракции, на котором видно, что оба метода представляют собой частные случаи обобщенной стратегии перемещения по графу — той, которая была предложена в реализацию поиска в ширину (программа 18.9).

Основной принцип прост: мы снова обращаемся к описанию поиска в ширину из раздела 18.6, только вместо понятия очередь (queue) используем обобщенный термин накопитель (fringe) — множество ребер-кандидатов для следующего включения в дерево поиска. Мы сразу же приходим к общей стратегии поиска связного компонента графа. Начав с петли исходной вершины в накопителе и пустого дерева, выполняем следующую операцию, пока накопитель не станет пустым:

Перенесите какое-либо ребро из накопителя в дерево. Если вершина, в которую оно ведет, еще не посещалась, посетите эту вершину и поместите в накопитель все ребра, которые ведут из этой вершины в еще не посещенные вершины.

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

Если для реализации накопителя использовать очередь, получится поиск в ширину, описанный в разделе 18.6. Если для реализации накопителя использовать стек, получится поиск в глубину. Это явление подробно представлено на рис 18.25, который полезно сравнить с рисунками 18.6 и 18.21.

Доказательство эквивалентности рекурсивного DFS и DFS на базе стека представляет собой интересное упражнение по удалению рекурсии, в процессе которого стек, лежащий в основе рекурсивной программы, фактически преобразовывается в стек, реализующий накопитель (см. упражнение 18.63). Порядок просмотра в DFS, показанный на рис 18.25, отличается от порядка просмотра на рис 18.6 только тем, что из-за дисциплины LIFO ребра, инцидентные каждой вершине, проверяются в порядке, обратном порядку в матрице смежности (или в списках смежности). Однако главное не меняется: если изменить структуру данных в программе 18.8 с очереди на стек (что легко сделать, поскольку интерфейсы АТД этих двух структур данных отличаются только именами функций), то программа будет выполнять поиск не в ширину, а в глубину.

Как было сказано в разделе 18.7, этот обобщенный метод может оказаться не таким эффективным, как хотелось бы, поскольку накопитель оказывается загроможден ребрами, указывающими на вершины, которые уже были перенесены в дерево, когда данное ребро находилось в накопителе. В случае очередей FIFO этого удается избежать благодаря пометке конечных вершин в момент занесения их в очередь. Мы игнорируем ребра, которые ведут в вершины, находящиеся в накопителе, поскольку знаем, что они не будут использованы: старое ребро (и посещенная вершина) извлекается из очереди раньше, чем новое (см. программу 18.9). В реализации со стеком все наоборот: когда в накопитель нужно поместить ребро с той же конечной вершиной, что и уже хранящееся ребро, мы знаем, что не будет использовано старое ребро, поскольку новое ребро (и посещенная вершина) извлекается из стека раньше старого. Чтобы охватить эти два крайних случая и обеспечить возможность реализации накопителя, которая может воспользоваться какой-нибудь другой стратегией, блокирующей наличие в накопителе ребер, которые указывают на ту же вершину, мы скорректируем нашу обобщенную схему следующим образом:

Выберите из накопителя ребро и перенесите его в дерево. Посетите вершину, в которую оно ведет, и поместите в накопитель все ребра, которые ведут из этой вершины в еще не посещенные вершины, руководствуясь стратегией замены в накопителе, которая гарантирует, что никакие два ребра в накопителе не указывают на одну и ту же вершину (ррис 18.26).

(рис 18.25) Алгоритм поиска в глубину с использованием стека

Вместе срис 18.21 данный рисунок демонстрирует, что поиски в ширину и в глубину отличаются друг от друга только рабочей структурой данных. Для поиска в ширину используется очередь, а для поиска в глубину — стек. Выполнение начинается с просмотра всех вершин, смежных с исходной вершиной (вверху слева). Затем мы перемещаем ребро 0-7 из стека в дерево и заталкиваем в стек инцидентные вершине 7 ребра 7-1, 7-4 и 7-6, которые ведут в еще не включенные в дерево вершины (вторая диаграмма сверху слева). Дисциплина LIFO предполагает, что при помещении ребра в стек другие ребра, ведущие в ту же вершину, считаются неактуальными и игнорируются, когда поднимаются в верхушку стека. Эти ребра заштрихованы на рисунке серым цветом. После этого мы переносим ребро 7-6 из стека в дерево и заносим инцидентные ему ребра в стек (третья диаграмма сверху слева). Потом мы извлекаем из стека ребро 4-6 и заносим инцидентные ему ребра, два из которых приводят нас к новым вершинам (внизу слева). В завершение поиска мы извлекаем из стека оставшиеся ребра, игнорируя " серые " ребра, когда они поднимаются в верхушку стека (справа).

Стратегия блокировки одинаковых конечных вершин в накопителе позволяет отказаться от проверки, была ли посещена конечная вершина извлеченного из очереди ребра. В случае поиска в ширину используется реализация очереди с правилом игнорирования новых элементов, а для поиска в глубину нужен стек с правилом игнорирования старых элементов. Однако любая обобщенная очередь в сочетании с любым правилом блокировки также даст эффективный метод просмотра всех вершин и ребер графа за линейное время с использованием объема дополнительной памяти, пропорционального V. Схематическая иллюстрация этих различий приведена на рис 18.27. Так что в нашем распоряжении имеется целое семейство стратегий поиска на графе, которое содержит и BFS, и DFS, и члены которого отличаются друг от друга только реализацией обобщенной очереди. Как мы увидим ниже, в это семейство входят и многие другие классические алгоритмы обработки графов.

В программе 18.10 представлена реализация этих идей для графов, представленных списками смежности. Она помещает ребра накопителя в обобщенную очередь и использует обычные векторы, индексированные именами вершин, для идентификации вершин в накопителе, чтобы можно было воспользоваться явной операцией АТД обновить, когда встречается другое ребро, ведущее в вершину, которая уже занесена в накопитель. Конкретная реализация АТД может выбирать, игнорировать ли ей новое ребро или заменить им старое ребро.

(рис 18.26) Терминология поиска на графе

Для выполнения поиска на графе мы используем дерево поиска (черные линии) и накопитель (серые линии), содержащие ребра, которые являются кандидатами на следующее включение в дерево. Любая вершина либо занесена в дерево (черные), либо находится в накопителе (серые), либо еще не просмотрена (белые). Вершины дерева соединены древесными ребрами, а каждая вершина из накопителя соединена ребром с некоторой вершиной дерева.

(рис 18.27) Стратегии поиска на графе

Здесь показаны различные возможности при выборе следующего шага поиска, показанного на рис 18.26. Мы переносим вершину из накопителя в дерево (из центра колеса, вверху справа), проверяем все ее ребра и помещаем ребра, ведущие в непроверенные вершины, в накопитель. При этом используется правило замещения, которое определяет обработку ребер, указывающих на вершины, которые уже присутствуют в накопителе и указывают на ту же самую вершину: нужно ли пропустить такое ребро или заменить им ребро из накопителя. В поиске в глубину мы всегда заменяем старые ребра, а в поиске в ширину — всегда игнорируем новые ребра; в других стратегиях мы заменяем одни ребра и пропускаем другие.

Программа 18.10. Обобщенный поиск на графе

Данный класс поиска на графе обобщает алгоритмы BFS и DFS и поддерживает другие алгоритмы обработки графов (см. , в котором обсуждаются эти алгоритмы и альтернативные реализации). В нем используется обобщенная очередь ребер, которая называется накопителем (fringe). Вначале в накопитель заносится петля исходной вершины; затем, пока накопитель не пуст, мы переносим из него ребро e в дерево (с началом в вершине e.v) и просматриваем список смежности вершины e.w, помещая в накопитель непросмотренные вершины и вызывая функцию update при появлении новых ребер, указывающих на вершины, которые уже занесены в накопитель.

Этот код использует векторы ord и st, чтобы никакие два ребра в накопителе не указывали на одну и те же вершину. Вершина v является конечной вершиной ребра, помещенного в накопитель, тогда и только тогда, когда она помечена (значение ord[v] не равно -1), но еще не находится в дереве (st[v] равно -1).

  #include "GQ.cc"
  template <class Graph>
  class PFS : public SEARCH<Graph>
    { vector<int> st;
      void searchC(Edge e)
        { GQ<Edge> Q(G.V());
          Q.put(e); ord[e.w] = cnt++;
          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++; }
              else
                if (st[t] == -1) Q.update(Edge(e.w, t));
            }
        }
    public:
      PFS(Graph G) : SEARCH<Graph>(G), st(G.V(), -1)
        { search(); }
      int ST(int v) const { return st[v]; }
    } ;
      

Лемма 18.12. Обобщенный поиск на графе посещает все вершины и ребра графа за время, пропорциональное V², для представления матрицей смежности и за время, пропорциональное V + E для представления списками смежности плюс, в худшем случае, время на V операций вставки, V операций удаления и E операций обновления в обобщенной очереди размера V.

Доказательство. Доказательство леммы 18.11 не зависит от реализации очереди и поэтому применимо и здесь. Указанные дополнительные затраты времени на операции с обобщенной очередью следуют непосредственно из программной реализации. $$$\blacksquare$$$

Существует множество других заслуживающих внимания эффективных моделей АТД накопителя. Например, как в случае нашей первой реализации BFS, можно придерживаться нашей первой общей схемы: просто поместить все ребра в накопитель, а при извлечении из накопителя игнорировать те их них, которые ведут в вершины, уже включенные в дерево. Недостаток такого подхода, как и в случае BFS, состоит в том, что максимальный размер очереди должен быть равен E, а не V. Либо можно выполнять обновления неявно в реализации АТД, просто указав, что никакие два ребра с одной и той же конечной вершиной не могут находиться в очереди одновременно. Однако простейший способ сделать это в реализации АТД по сути эквивалентен использованию вектора, индексированного именами вершин (см. упражнения 4.51 и 4.54), поэтому такая проверка больше вписывается в клиентские программы, выполняющие поиск на графе.

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

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

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

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

template <class Item>
class GQ
  { private:
      vector<Item> s; int N;
    public:
      GQ(int maxN) : s(maxN+1), N(0) { }
      int empty() const 
        { return N == 0; }
      void put(Item item)
        { s[N++] = item; }
      void update(Item x) { }
      Item get()
        { int i = int(N*rand()/(1.0+RAND MAX));
          Item t = s[i];
          s[i] = s[N-1];
          s[N-1] = t;
         return s[--N]; }
  };
      

(рис 18.28) Размеры накопителя при работе поиска в глубину, рандомизированного поиска и поиска в ширину

Эти графики размеров накопителя во время поисков, представленных на рис 18.13, рис 18.24 и рис 18.29, показывают, какое огромное влияние оказывает на поиск на графе выбор структуры данных для накопителя. При использовании стека в DFS (вверху) накопитель заполняется в самом начале поиска, поскольку на каждом шаге мы находим новые узлы, а затем извлекаем из накопителя все его содержимое. При использовании рандомизированной очереди (в центре) максимальный размер очереди намного меньше. При использовании очереди FIFO в BFS (внизу) максимальный размер очереди еще меньше, а новые узлы обнаруживаются в процессе поиска.

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

Все обобщенные алгоритмы поиска на графах просматривают каждое ребро всего один раз и в худшем случае требуют дополнительного объема памяти, пропорционального V; однако они все же различаются некоторыми показателями производительности. Например, на рис 18.28 показано, как меняется размер накопителя в процессе выполнения поиска в глубину, в ширину и рандомизированного поиска; на рис 18.29 показано дерево, вычисленное с помощью рандомизированного поиска для примера, представленного на рис 18.13 и рис 18.24. Для рандомизированного поиска не характерны ни длинные пути, как в DFS, ни узлы с большими степенями, как в BFS. Формы этих деревьев и графиков размеров накопителя зависят от структуры конкретного графа, на котором производится поиск, но они все-таки характеризуют различные алгоритмы.

Поиск на графах можно обобщить и далее, если работать с лесом (а не только с деревом). Мы уже вплотную пошли к этому уровню абстракции, однако отложим рассмотрение ряда таких алгоритмов до .

(рис 18.29) Граф рандомизированного поиска

Здесь показан процесс рандомизированного поиска на графе (слева) в том же стиле, что и на рисунках 18.13 и 18.24. Форма дерева поиска находится где-то между поиском в глубину и поиском в ширину. Динамические характеристики этих трех алгоритмов, которые отличаются только структурой данных, необходимой для выполнения работы, разительно отличаются.

Упражнения

18.61. Проанализируйте преимущества и недостатки реализации обобщенного поиска на графе на базе следующего правила: " Перенесите ребро из накопителя в дерево. Если вершина, в которую оно ведет, не посещалась, посетите эту вершину и занесите в накопитель все инцидентные ей ребра " .

18.62. Разработайте реализацию АТД графа, представленного списками смежности, которая содержит ребра (а не только их конечные вершины) в списках. Затем реализуйте поиск на графе, основанный на стратегии из упражнения 18.61, который посещает каждое ребро, но разрушает граф, воспользовавшись тем, что ребра всех вершин можно перемещать в накопитель с помощью изменения лишь одной ссылки.

18.63. Докажите, что рекурсивный поиск в глубину (программа 18.3) эквивалентен обобщенному поиску на графе с использованием стека (программа 18.10) в том смысле, что обе программы посещают все вершины любого графа в одном и том же порядке тогда и только тогда, когда эти программы просматривают списки смежности в разных направлениях.

18.64. Приведите три различных порядка обхода при рандомизированном поиске на графе

3-71-47-80-55-23-82-90-64-92-66-4.

18.65. Может ли рандомизированный поиск посетить вершины графа 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4.

в порядке возрастания их индексов? Обоснуйте свой ответ.

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

18.67. Разработайте алгоритм рандомизированного поиска на графе, который с равной вероятностью выбирает из накопителя любое ребро. Указание. См. программу 18.8.

18.68. Опишите стратегию обхода лабиринта, которая соответствует использованию обычного стека магазинного типа для обобщенного поиска на графе (см. раздел 18.1).

18.69. Добавьте в обобщенный поиск на графе (см. программу 18.10) возможность вывода значений высоты дерева и процента обработанных ребер для каждой просматриваемой вершины.

18.70. Эмпирически определите средние значения величин, описанных в упражнении 18.69, для обобщенного поиска на графе с использованием случайной очереди в графах различных размеров и построенных на основе различных моделей (см. упражнения 17.64—17.76).

18.71. Реализуйте производный класс, который строит динамические графические анимации обобщенного поиска на графах, в которых с каждой вершиной связаны координаты (x, у) (см. упражнения 17.55—17.59). Протестируйте полученную программу на случайных евклидовых графах с соседними связями, используя столько точек, сколько сможете обработать за приемлемый промежуток времени. Ваша программа должна строить изображения вроде диаграмм на рис 18.13, рис 18.24 и рис 18.29, хотя для обозначения вершин и ребер, которые находятся в дереве, или в накопителе, или еще не просмотрены, вместо оттенков серого можно использовать различные цвета.

Анализ алгоритмов на графах

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

Как было кратко отмечено в , мы стремимся (в идеальном случае) получить естественные модели входных данных, обладающие тремя важными свойствами:

Они достаточно точно соответствуют реальным данным, чтобы использовать их для прогнозирования производительности.

Они достаточно просты, чтобы подвергнуть их математическому анализу.

Можно написать генераторы экземпляров задач, которые можно использовать для тестирования наших алгоритмов.

При наличии этих трех компонентов можно приступать к циклу проектирования, анализа, реализации и тестирования, который позволяет создавать эффективные алгоритмы для решения практических задач.

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

Математический анализ очень труден, и поэтому многие аналитические вопросы остаются без ответа.

Существует очень много различных видов графов, и невозможно достаточно полно протестировать наши алгоритмы на всех этих видах.

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

Из-за сложности графов часто не удается в полной мере оценить существенные свойства графов, с которыми приходится сталкиваться на практике, или искусственных графов, которые мы (возможно) можем генерировать и анализировать.

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

Однако если время выполнения алгоритма зависит от структуры входного графа, прогнозы становятся не таким простым делом. Но если понадобится обработать очень много больших графов, то нам нужны эффективные алгоритмы по той же причине, по какой они требуются и в любой другой проблемной области. Поэтому мы продолжим изучение основных свойств алгоритмов и их применений и постараемся выявить методы, наиболее удобные для обработки графов, которые могут встретиться на практике.

Для иллюстрации некоторых из этих вопросов мы вернемся к изучению свойства связности графа — т.е. к задаче, которую мы начали рассматривать еще в главе 1 . Связность случайных графов привлекала к себе внимание математиков в течение многих лет, и данной теме посвящена обширная литература. Эта литература выходит за рамки настоящей книги, однако она представляет собой фон, который оправдывает использование этой задачи как основы для некоторых экспериментальных исследований, углубляющих наше понимание базовых алгоритмов и изучаемых видов графов.

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

Лемма 18.13. Если $$$E>\dfrac{1}{2}V\ln{V}+\mu V$$$ (при положительном $$$\mu $$$), то случайный граф с V вершинами и E ребрами состоит из одного связного компонента и изолированных вершин, среднее количество которых не превышает $$$e^{-2\mu}$$$, с вероятностью, приближающейся к 1 при бесконечном возрастании V.

Доказательство. Этот факт был установлен в пионерской работе Эрдеша (Erdos) и Реньи (Renyi) в 1960 г. Само доказательство выходит за рамки данной книги (см. раздел ссылок). $$$\blacksquare$$$

На основании этой леммы можно ожидать, что крупные неразреженные случайные

графы являются связными. Например, если V> 1000 и E > 10V, то $$$\mu >10-\dfrac{1}{2}\ln{1000}>6,5$$$, и среднее количество вершин, не содержащихся в гигантском компоненте, (почти наверняка) меньше, чем $$$e^{-13}<0,000003$$$. Если сгенерировать миллион случайных графов с 1000 вершинами и плотностью, большей 10, то среди них могут оказаться несколько графов с одной изолированной вершиной, но остальные графы будут связными.

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

Из таблицы 18.1 видно, что эти структурные различия между случайными графами и графами с соседними связями сохраняются и тогда, когда V и E находятся в пределах, представляющих практический интерес. Конечно, такие структурные различия могут отразиться на производительности алгоритмов.

(рис 18.30) Связность в случайных графах

Здесь показаны 10 этапов эволюции двух видов случайных графов при добавлении 2E ребер в первоначально пустые графы. Каждый график представляет собой гистограмму количества вершин в компонентах размером от 1 до V— 1 (слева направо). Вначале все вершины содержатся в компонентах размером 1, а в конце практически все вершины входят в один гигантский компонент. Графики слева соответствуют обычному случайному графу: гигантский компонент формируется быстро, а все другие компоненты малы. Графики справа соответствуют случайному графу с соседними связями: компоненты различных размеров сохраняются в течение более длительного времени.

Связность на примере двух моделей случайного графа

E	Случайные ребра		Случайные ребра из 10 соседних
	C	L	C	L
1000	99000	5	99003	3
2000	98000	4	98010	4
5000	95000	6	95075	5
10000	90000	8	90300	7
20000	80002	16	81381	9
50000	50003	1701	57986	27
100000	16236	79633	28721	151
200000	1887	98049	3818	6797
500000	4	99997	19	99979
1000000	1	100000	1	100000

Обозначения:
C	Количество связных компонентов
L	Размер наибольшего связного компонента

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

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

Во-первых, из таблицы ясно, что не следует использовать представление матрицей смежности для больших разреженных графов (и невозможно для очень больших) — не только из-за неподъемных затрат на инициализацию матрицы, но и потому, что алгоритм просматривает каждый элемент матрицы, вследствие чего время его выполнения пропорционально размеру матрицы (V²), а не количеству единиц в ней (E). Например, из таблицы следует, что в случае использования матрицы смежности на обработку графа с 1000 ребрами нужно примерно столько же времени, что и на обработку графа, содержащего 100 000 ребер.

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

Эмпирическое сравнение алгоритмов поиска на графе

E	U	U*	Матрица смежности			Списки смежности
			I	D	D*	I	D	D*	B	B*
5000 вершин
500	1	0	255	312	356	1	0	0	0	1
1000	0	1	255	311	354	1	0	0	0	1
5000	1	2	258	312	353	2	2	1	2	1
10000	3	3	258	314	358	5	2	1	2	1
50000	12	6	270	315	202	25	6	4	5	6
100000	23	7	286	314	181	52	9	2	10	11
500000	117	5	478	248	111	267	54	16	56	47
100000 вершин
5000	5	3				3	8	7	24	24
10000	4	5				6	7	7	24	24
50000	18	18				26	12	12	28	28
100000	34	35				51	28	24	34	34
500000	133	137				259			88	89

Обозначения:
U	Взвешенное быстрое объединение со сжатием пути делением пополам (программа 1.4)
I	Начальное создание представления графа
D	Рекурсивный DFS (программа 18.3)
B	BFS (программа 18.9)
*	Выход сразу при установлении полной связности графа

В этой таблице показаны относительные значения времени определения различными алгоритмами количества связных компонентов (и размера наибольшего из них) для графов с различным количеством вершин и ребер. Как и ожидалось, алгоритмы, которые используют представление матрицей смежности, медленно работают на разреженных графах, но вполне конкурентоспособны на насыщенных графах. В случае данной задачи алгоритмы объединения-поиска, которые были рассмотрены в , работают быстрее всего, т.к. они строят структуру данных, предназначенную специально для решения данной задачи, а поэтому не нуждаются в другом представлении графа. Но если структура данных, представляющая граф, уже построена, то алгоритмы DFS и BFS оказываются быстрее и гибче. Добавление проверки для прекращения работы, когда уже понятно, что граф представляет собой единый связный компонент, существенно повышает быстродействие поиска в глубину и объединения-поиска (но не поиска в ширину) при обработке насыщенных графов.

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

В-четвертых, эта таблица показывает, что метод на основе объединения-поиска, описанный в , работает быстрее поисков в глубину и в ширину — главным образом потому, что ему не нужно представление всего графа. Однако, не имея такого представления, мы не можем дать ответ на такие простые запросы, как " Существует ли ребро, соединяющее вершины v и w? " . Поэтому методы на основе объединения-поиска не годятся, если мы хотим получить больше, чем то, для чего они предназначены (например, ответы на запросы типа " Существует ли путь, соединяющий вершины v и w? " вперемешку с добавлением ребер). Если внутреннее представление графа уже построено, не стоит трудиться над реализацией алгоритма объединения-поиска только для того, чтобы узнать, связен граф или нет, поскольку и DFS, и BFS могут дать ответ так же быстро.

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

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

Упражнения

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

18.73. Составьте на основе эмпирических исследований таблицу наподобие таблицы 18.2 для задачи определения, является ли граф двусвязным.

18.74. Определите эмпирически ожидаемый размер второго по величине связного компонента разреженных графов различных размеров, построенных на основе различных моделей (см. упражнения 17.64—17.76).

18.75. Напишите программу для построения графиков наподобие рис 18.30 и протестируйте ее на графах различных размеров, построенных на основе различных моделей (см. упражнения 17.64—17.76).

18.76. Измените программу из упражнения 18.75, чтобы она строила аналогичные гистограммы для размеров реберно-связных компонентов.

18.77. Числа в таблицах, приведенных в данном разделе, получены при исследовании только одной выборки. Можно подготовить аналогичную таблицу, каждый элемент которой будет получен на основе 1000 экспериментов, и подсчитать среднее значение и среднеквадратичное отклонение для каждой выборки (хотя таблица станет слишком большой). Будет ли такой подход более эффективен? Обоснуйте свой ответ.