Обход - граф
Cтраница 2
Теперь мы можем перейти к описанию процедуры обхода графа С /, которая представляет собой линеаризацию во времени процесса поиска при помощи графа U. [16]
Каждая строка Н - матрицы составляется путем обхода графа от данной узловой точки в базовую точку через ветви дерева. [17]
Более эффективные алгоритмы отыскания бикомпонент основаны на обходе графа, реализующего поиск в глубину. В основе их лежат утверждения, в формулировке которых будем предполагать, что бикомпонента может состоять из одной вершины. [18]
Контур выделяется, как только оп обнаруживается в результате обхода графа. [19]
Следовательно, вместо проверки порядков вершин В-ГСС ( что требуется для обхода графа) можно проверять порядки вершин К-ГСС. Выбор такого способа обладает двумя практическими преимуществами. Во-первых, появляется возможность комбинировать алгоритмы, основанные на критериях четности и связности, а во-вторых - возможность увеличения скорости решения. Определение порядка вершин графа требует одновременного просмотра трех строк. В случае В-ГСС эти строки могут быть достаточно длинными, в то время как интервалы контура обычно оказываются существенно более короткими. В связи с возможностью комбинации алгоритмов мы будем пользоваться К-ГСС при применении алгоритмов обоих типов. [20]
 |
Огпсаниеизображения, приведенного на. [21] |
Мы не приводим в явном виде алгоритм построения указанных описаний, поскольку обход графа может осуществляться различными способами, выбор одного из которых определяется характером решаемой задачи. [22]
Назовем обход графа, соответствующий поиску в глубину, стандартным обходом; траекторию обхода графа будем обозначать Q, начало обхода - буквой а. Начальная вершина выбирается произвольно. Первый ход по ребру, во время которого его конец получает М - номер, назовем прямым ходом, второй - в противоположном направлении - обратным. Условимся, что прямой ход задает ориентацию ребер, связанную с данным обходом. Основное свойство стандартного обхода в данном случае состоит в том, что, войдя в ветвь блоков G по ребру и, мы находимся внутри G до тех пор, пока не обойдем ее полностью, заканчивая движение по G обратным ходом по и. [23]
В качестве заключительного примера в этой глале рассмотрим одну из важных рекурсивных программ: рекурсивный обход графа, изи приск в ыуйину ( depih-first senrzk) - Этот метод симметричною посещения всех у лов графа - непосредственное о & оСшснлс методов обход деревьев, рассмотренных в раздое 5.6, и он служит основой для многих базовых алгоритмов обработки графов ( с. [24]
Подобно тому как это было сделано в случае с обходом дерева, можно определить метод обхода графа, при котором используется явный стек, как показано на рис. 5.34. Моно представить себе абстрактный стек, содержащий двойные записи: узел и указатель на список смежности для этого узла. Когда стек инициализируется начальным узлом, а указатель - первым элементом списка смежности для этого узла, алгоритм поиска в глубину эквивалентен входу в цикл, в котором сначала посещается узел в верхней части стека ( если он еще не был посещен); затем сохраняется узел, указанный текущим указателем списка смежности; далее, ссылка из списка смежности обновляется следующим узлом ( с выталкиванием записи, если достигнут конец списка смежности); и, наконец, запись стека для сохраненного узла заталкивается со ссылкой на первый узел его списка смежности. [25]
При просмотре этого графа каждому ребру приписывается ориентация, в котором оно проходится, когда осуществляется обход графа G. Вообще говоря, дуги графа G, не включенные в остовное дерево, соединяют маршруты этого дерева. [26]
Поскольку для фоновых алгоритмов важны порядок и моменты появления записей в ответе, определим некоторую процедуру обхода графа С /, который в дальнейшем поможет определить новое понятие сложности нашей графа. [27]
Если указанные выше условия выполнены, то задача имеет, как правило, не одно решение - обходов графа может быть довольно много, но число пройденных при этом ребер будет всегда одним и тем же. [28]
Точки сочленения можно обнаружить с помощью грубой силы, удаляя из графа поочередно каждую вершину и пользуясь одним из наших алгоритмов обхода графа для проверки связности оставшейся части. Если оставшийся граф связен, то удаленная вершина не является точкой сочленения. При таком подходе мы должны выполнить N обходов графа с N вершинами, что потребует 0 ( 7V2) операций. Однако сохраняя незначительное количество дополнительной информации при обходе графов, можно обнаружить все точки сочленения и компоненты двусвязности при единственном обходе. [29]
При выполнении расчетов исходные данные могут быть представлены в виде описания собственного графа системы, на основе которого используются алгоритмы анализа обхода графа, контроля достоверности информации и параметров, определяющих технологию транспорта газа. [30]
Страницы: 1 2 3 4