Метка - вершина
Cтраница 3
Включение нового слова соответствует подвешиванию к дереву новой вершины, меткой которой было бы новое слово, без нарушения свойства дерева быть бинарным. Для отыскания места подвешивания новой вершины будем двигаться, начиная с корня и сравнивая включаемое слово с метками проходимых вершин: если метка совпадает с включаемым словом, то ничего делать не надо, так как слово уже в словаре; если метка больше нового слова, то движемся к потомку вершины по левой дуге, в противном случае - по правой. Если слова в словаре нет, то мы попадаем в вершину, у которой отсутствует один или оба потомка; к ней мы и подвешиваем новую вершину. [31]
Позже мы будем просто рисовать графы, а не задавать их множествами. Вершины будут изображаться кружочками, а ребра - отрезками линий. Внутри кружочков будут записаны метки вершин. Ребра ориентированного графа будут снабжены стрелками, указывающими допустимое направление движения по ребру. [32]
С в орграф G, состоящий из IV. IVI 1 обратных ребер, как говорилось в разд. С этого момента будем игнорировать исходные метки вершин и обозначать вершины их значениями пит. [33]
Реализация рассмотренной схемы поиска кратчайшего пути представлена в алгоритме 6.11, где граф Г ( X, U, Ф) представляется матрицей весов We [ w - ], веса несуществующих ребер полагаются равными оо. Вектор Mark [ x ] меток вершин устанавливает принадлежность вершины х е постоянной ( TRUE) или временной ( FALSE) метке. Вектор Dist [ x ] в алгоритме фиксирует текущие значения меток вершин. Вектор Prev [ x ] позволяет восстановить в обратной последовательности вершины кратчайшего пути. [34]
Пусть Я есть DDA-граф с базой G для R - у U. Существует метод вычисления chasea ( Тк), напоминающий построение Я. Сходство состоит в том, что если У есть множество меток вершин на некотором шаге построения Я, то строка, соответствующая w в некотором табло порождающей последовательности для TR, имеет выделенные переменные во всех столбцах, входящих в У. [35]
Оценим число различных программ, состоящих из данного числа команд. Каждый такой граф зададим списком из девяти условий, которые будут определять его вершины, ребра и метки вершин и ребер. [36]
 |
Параметризация формы куба. [37] |
В случае многогранной поверхности параметрический и размерный графы составляются на множестве вершин, ребер и граней фигуры. Среди этих параметров есть линейные и угловые. На рис. 118 и 119 показаны параметрические графы линейных и угловых параметров, в совокупности составляющих параметрический граф куба. Линейный параметрический граф имеет вершины, нагруженные метками вершин и их координатами. [38]
Рассмотрим алгоритм нахождения числа компонент связности, а также выделения этих компонент на неориентированном графе. Подобным образом решается задача и для ориентированного графа. Структура алгоритма 6.3 является модификацией в сторону упрощения основного алгоритма 6.1 поиска в глубину. Работа алгоритма 6.3 направлена на формирование вектора Mark [ x ] меток вершин х е X графа. [39]
Таким образом, для определения точки сочленения выхода из блока достаточно найти вершину этого блока с минимальной меткой. Свойство циклической замкнутости блока позволяет это сделать лишь на основе вектора меток Mark [ x ], не привлекая дополнительной информации. На рис. 6.44 схематично представлен блок, где вершина w - точка входа в блок и точка сочленения. Поэтому, сохраняя минимальное значение меток обследованных вершин ( включая и по обратным ребрам поиска в глубину), будем проверять при рекурсивном выходе из поиска в глубину совпадает ли это минимальное значение с меткой вершины выхода. Если ответ положительный, то найдена точка сочленения. В алгоритме значения минимальных меток фиксируются в векторе Virtual [ x ] для каждой вершины х е X, как наименьшее значение из Mark [ y ], где у - вершины графа, которые достижимы из х при проходе графа в глубину. [40]
Метод поиска в глубину на простом неориентированном графе представлен в алгоритме 6.1. Рекурсивная процедура Depth ( x, w) осуществляет поиск в глубину на графе Г ( X, U, Ф), содержащем х е X, и строит для графа дерево Т поиска, которое является ориентированным остовным деревом Го ( X, Т, Ф) ( если исходный граф не связен, то Г0 будет лесом); w e является отцом х е Хв строящемся дереве, где х - исследуемая вершина. Граф задан структурой смежности Adj [ x ], где Adj [ x ] означает множество вершин, смежных с х е X. Элементы Т - это ребра строящегося дерева поиска, а элементы В - это обратные ребра, которые не могут принадлежать Г0, так как они ведут назад в пройденные ранее вершины. Заметим, что обратное ребро должно идти от потомка к предку по дереву поиска. Чтобы отличить уже пройденные вершины от непройденных, вводится вектор Mark [ x ] меток вершин, которые постепенно нумеруются от 1 до Х по мере того, как попадаем в них. Сначала полагается Mark [ x ] О для всех х е X в знак того, что ни одна вершина не пройдена, и когда попадаем в вершину х первый раз, Mark [ x ] получает ненулевое значение. [41]
Страницы: 1 2 3