![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. Многие функции обработки графов основаны на использовании векторов, индексируемых именами вершин
В качестве соглашения будем полагать, что все векторы, индексированные именами вершин, инициализируются в функциях поиска на графе минус единицей (-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.
|