Часть 5. Алгоритмы на графах. Многие функции обработки графов основаны на использовании векторов, индекси­руемых именами вершин

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

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

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