Обход - граф
Cтраница 1
Обход графа, при котором на каждом шаге выбирается последовательно подграф слева направо и снизу и далее по направлению к корневой вершине. [1]
Обход графа двухуровневого изображения, содержащего его остов производится с помощью алгоритма 6.2 или аналогичного ему. Помимо стека 5 предусматривается буферная память Т, в которую заносятся координаты всех пикселов, соответствующих вершинам второго порядка. Если порядок некоторой вершины отличается от двух, координаты соответствующей точки выводятся и проверяется наличие точек в буферной памяти. Если какие-либо точки в ней обнаруживаются, выводится их описание, а также координаты точки, соответствующей последней просмотренной вершины, порядок которой отличается от двух. [2]
Назовем обход графа, соответствующий поиску в глубину, стандартным обходом; траекторию обхода графа будем обозначать Q, начало обхода - буквой а. Начальная вершина выбирается произвольно. Первый ход по ребру, во время которого его конец получает М - номер, назовем прямым ходом, второй - в противоположном направлении - обратным. Условимся, что прямой ход задает ориентацию ребер, связанную с данным обходом. Основное свойство стандартного обхода в данном случае состоит в том, что, войдя в ветвь блоков G по ребру и, мы находимся внутри G до тех пор, пока не обойдем ее полностью, заканчивая движение по G обратным ходом по и. [3]
При обходе графа по уровням мы, после посещения первого узла, посещаем все соседние с ним вершины. При втором проходе посещаются все вершины на расстоянии двух ребер от начальной. При каждом новом проходе обходятся вершины, расстояние от которых до начальной на единицу больше предыдущего. В графе могут быть циклы, поэтому не исключено, что одну и ту же вершину можно соединить с начальной двумя различными путями. [4]
При обходе графа по ширине просмотр вершин дерева ведется по этажам, переход к вершинам следующего этажа производится только после просмотра всех вершин данного этажа. [5]
При выполнении обхода графа по этим правилам мы стремимся проникнуть в глубь графа так далеко, как это возможно, затем отступаем на шаг назад и снова стремимся пройти вперед и так далее. [6]
Напишите программу обхода графа, обеспечивающую определение пар вершин, соединенных маршрутом, который содержит только вершины второй степени. Этот граф можно рассматривать как сеть связи, в которой вершины первой степени выполняют роль оконечных станций, вершины степени больше двух - аппаратуры обмена данными и вершины второй степени - усилителей. [7]
Иногда при обходах графа или при движении по ребрам из одной вершины в другую мы будем говорить о начале ребра и его конце, подразумевая при этом, что направление движения создает ориентацию ребра. В графе каждая пара вершин соединена не более чем одним ребром; допущение параллельных ребер приводит к новой конструкции, именуемой мульти-графом. [8]
Интересные задачи связаны с построением полных обходов графа. В термин полный обход мы можем вкладывать различное содержание, и это приводит к различным задачам. Более простой из них является задача построения обхода, содержащего все дуги графа. [9]
Далее ( блок 9) следует обход графа с выполнением гидравлических расчетов участков и увязкой давлений в узлах. [10]
Для решения задачи В разработан алгоритм обхода графа газопроводной сети по узлам. [11]
При выявлении эйлеровых цепей мы будем осуществлять обходы графа, двигаясь от одних вершин к Другим по соединяющим их ребрам. В связи с этим вводится понятие валентности вершины. [12]
Теперь мы можем перейти к описанию процедуры обхода графа t /, которая представляет собой линеаризацию во времени процесса поиска при помощи графа U. [13]
 |
Пример обхода графа в глубину. [14] |
Рассмотрим пример расчета по программе алгоритма 6.2 обхода графа, представленного на рис. 6.13. Сплошными линиями отмечены ребра, которые были пройдены во время обхода графа в глубину, пунктирными - обратные ребра. [15]
Страницы: 1 2 3 4