Компьютерные книги
Главное меню
Главная Поиск по сайту Добавить материал О нас Карта книг Карта сайта
Реклама
computersbooks.net -> Добавить материал -> Языки программирования -> Кубенский А.А. -> "Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++" -> 115

Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ - Кубенский А.А.

Кубенский А.А. Структуры и алгоритмы обработки данных. Объектно-ориентированный подход и реализация на C++ — Спб.: БВХ-Петербург , 2004. — 464 c.
ISBN 5-94157-506-8
Скачать (прямая ссылка): strukturiialgoritmiobrabotkidannih2004.djvu
Предыдущая << 1 .. 109 110 111 112 113 114 < 115 > 116 117 118 119 120 121 .. 161 >> Следующая

Как и в случае обхода деревьев, для графов существуют два основных класса обходов: обходы в глубину и обходы в ширину.
Обходы в глубину пытаются каждый раз после прохождения некоторой вершины А выбрать в качестве следующей такую вершину 5, в которую из вершины А ведет дуга. Таким образом, алгоритмы этого класса пытаются всегда двигаться вглубь графа, находя все новые не пройденные ранее вершины. Если таких непройденных вершин нет, то алгоритм возвращается к предыдущей, ранее пройденной вершине, и пытается найти очередную дугу, ведущую из нее в какую-либо другую еще не пройденную вершину. Если и таких вершин нет, то снова происходит откат назад, и так до тех пор, пока либо все вершины не будут пройдены, либо алгоритм вернется назад в вершину, выбранную в качестве исходной.
Обходы в ширину пытаются, начав с некоторой вершины, в качестве очередных рассматривать только вершины, непосредственно связанные с исходной. Только после того, как все такие вершины будут рассмотрены, алгоритм будет пытаться рассматривать следующий слой вершин, непосредственно связанных с только что пройденными. Таким образом, алгоритм обхода в ширину последовательно рассматривает все более удаленные от исходной вершины до тех пор, пока либо все вершины не будут пройдены, либо не останется больше вершин, достижимых из исходной.
Алгоритмы обхода графов (так же, как и деревьев, и списков) могут быть реализованы как внешними, так и внутренними итераторами. Внешний итератор в момент создания берет представление графа в качестве аргумента, а затем осуществляет последовательную выдачу номеров вершин графа, ис-
Алгоритмы обработки графов
329
пользуя для обхода локальные объекты, такие, как стек или очередь. Внутренний итератор чаще всего реализуется в виде рекурсивной функции, которая, проходя по очереди вершины графа, выполняет для каждой из них некоторое действие, заданное в качестве аргумента итератора.
Рассмотрим в качестве примера граф, изображенный на рис. 6.1.
Этот граф содержит 9 вершин и 12 дуг. Он состоит из двух компонент связности, так что заведомо не удастся обойти его весь, выбрав некоторую вершину в качестве исходной и проходя только по направлениям дуг. Тем не менее если сначала выбрать в качестве исходной вершины вершину 1, то все остальные вершины одной компоненты связности из нее будут достижимы, так что по крайней мере эта компонента связности будет пройдена до того, как потребуется вновь выбирать начальную вершину. Тем же свойством обладают и все остальные вершины графа, кроме вершины 7. Если выбрать ее в качестве начальной вершины для обхода, то будет пройдена только она сама, а потом потребуется вновь выбирать некоторую вершину в качестве начальной для обхода остальных.
Если в качестве алгоритма обхода взять алгоритм обхода в глубину, причем договориться, что из всех возможных альтернатив он всегда выбирает проход к вершине с наименьшим номером, то получится следующий порядок обхода вершин графа:
0; 1; 4; б; 3; 7; 2; 8; 5
Порядок обхода в ширину в данном случае отличается от порядка обхода в глубину незначительно:
0; 1; 4; б; 7; 3; 2; 8; 5
Но это, конечно, получается просто потому, что граф, выбранный нами для примера, очень небольшой. Обычно в случае больших графов порядки обхода отливаются весьма существенно.
330
Гпава 6
На рис. 6.1 изображена логическая структура графа. Для того чтобы яснее представить себе работу алгоритмов обхода, необходимо хорошо представлять также и физическую структуру памяти соответствующего объекта. В представлении графа рис. 6.1 в виде 1-графа имеются 9 списков дуг (для каждой вершины существует список исходящих из нее дуг). На рис. 6.2 приведено физическое представление этого графа.
На этом рисунке изображен массив списков дуг (около каждого элемента массива показан номер соответствующей вершины графа). Дуги представлены прямоугольниками, содержащими номер той вершины, в которую дуга входит.
В качестве первого примера рассмотрим внешний итератор вершин графа при обходе в глубину. Для этого определим класс, объекты которого получают исходный граф в виде аргумента конструктора, и затем осуществляют его обход, реализуя обычный интерфейс итератора. Для того чтобы перейти от текущей вершины графа к следующей, итератор должен, во-первых, запоминать, какие из вершин уже пройдены, а во-вторых, для быстрого возврата к предыдущей вершине помнить последовательность дуг на пути из выбранной начальной вершины в текущую. Эту последовательность дуг нам будет удобно представлять в виде стека, элементами которого будут содержать информацию, необходимую для возврата по дугам.
Алгоритмы обработки графов
331
Пусть алгоритм выбрал в качестве начальной вершину с номером 0. Тогда обход графа начнется в ситуации, приведенной в первой строке табл. 6.1.
Таблица 6.1. Последовательность состояний при обходе графа в глубину
Шаг Список пройденных вершин Текущая вершина Стек дуг на пути к текущей вершине
1 — 0 —
2 0 1 0-1
3 0,1 4 0—1, 1—4
4 0, 1,4 6 0—1, 1—4, 4—6
5 0, 1,4,6 3 0—1, 1-4, 4-6, 6-3
6 0, 1,4, 6,3 7 0—1, 1-4, 4-7
Предыдущая << 1 .. 109 110 111 112 113 114 < 115 > 116 117 118 119 120 121 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Вирт Н. "Систематическое программирование " (Теория программирования)

Эком "Microsoft Excel 2000 шаг за шагом Русская версия самоучитель " (Самоучитель)

Поляков А.Ю. "Методы и алгоритмы компьютерной графики в примерах Vizual C++" (Графика)

Баяковский Ю.М. "Графическая библиотека Open GL " (Графика)

Валиков А. "Технология " (Языки программирования)
Авторские права © 2013 ComputersBooks. Все права защищены.