Cтраница 5
Напомним, что корневое дерево с п 1 вершинами - это связный неориентированный граф, не содержащий циклов, с одной выделенной вершиной, называемой корнем, и с п некорневыми вершинами. Корневое дерево с п 1 вершинами имеет п ребер. В дальнейшем все ребра дерева считаются направленными от корня и кратность вершины равна числу выходящих из нее ребер. [61]
Сущность алгоритма состоит в том, что на любом этапе построения связывающего дерева допускается выполнение одной из следующих операций: 1) всякая изолированная точка ( еще не связанная с другими точками) соединяется с ближайшей соседней точкой, удаленной от данной на расстояние не больше, чем другие точки; 2) всякая изолированная совокупность точек ( подмножество точек, связанных между собой) соединяется с ближайшей соседней точкой кратчайшим ребром. V вершинами осуществляется за ( jV - 1) последовательных шагов. На каждом шаге добавляется новое ребро дерева. Указанный алгоритм непосредственно непригоден для трассировки внутрицеховых ТП, так как не учитывает технологические и конструкционные ограничения трассировки, что, в свою очередь, приводит к нереализуемым вариантам решения. На втором этапе определяется, в каком слое печатной платы наиболее эффективно прокладывать каждое соединение. На третьем этапе устанавливается порядок прокладки соединений в каждом слое с учетом результатов второго этапа. Четвертый этап является основным, наиболее трудоемким, определяющим эффективность и качество решения задачи трассировки в целом. [62]
Метод поиска в глубину на простом неориентированном графе представлен в алгоритме 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 ] получает ненулевое значение. [63]