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

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

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

ГЛАВА 6
Алгоритмы обработки графов
В этой главе представлены некоторые классические алгоритмы обработки графов и приведены примеры их использования. Алгоритмы на графах традиционно относятся к наиболее сложным алгоритмам, в этой области было получено много интересных результатов. Большое количество литературы посвящено описаниям этих алгоритмов, достаточно упомянуть такие фундаментальные работы, как [1], [7] и [8]. В нашу задачу не входит глубокий анализ этих алгоритмов, мы даже не будем пытаться находить во всех случаях оптимальные решения. Задача этой главы состоит в том, чтобы определить, как выбранное представление данных влияет на выбор алгоритмов, и, кроме того, интересно посмотреть, как реализуются классические алгоритмы на языке C++ с применением современных технологий создания программ.
6.1. Обходы и поиск в графах
Основу многих алгоритмов обработки сетевой информации составляют алгоритмы обхода (итерации) графов, в процессе которого производится поиск необходимой информации или определение каких-либо характеристик сети. Если граф имеет N вершин и М дуг, то говорят, что алгоритм обхода индуцирует нумерацию вершин и дуг графа, приписывая им номера от 1 до N и от 1 до М соответственно в порядке обхода. Итераторы графа могут быть как внешними, так и внутренними, при этом внешний итератор, как обычно, выдает вершины или дуги графа в порядке обхода, а внутренний итератор, обходя граф, посещает его вершины и дуги и выполняет в каждой из них процедуру посещения.
В процессе обхода обычно используется информация о связях между вершинами, т. е. алгоритмы обхода, просматривая граф, переходят всегда от некоторой вершины к одной из связанных с нею вершин. Разумеется, это не обя-
Алгоритмы обработки графов
327
зательно означает, что порядок обхода вершин также таков, что вслед за одной вершиной непременно в качестве следующей вершины следует одна из связанных с ней. Более того, в большинстве случаев такой обход построить просто невозможно. Обходы, описанные выше, называются Гамильтоновыми путями, для существования Гамильтонова пути граф должен удовлетворять определенным условиям. Но алгоритмы обхода просто используют связи между вершинами для перехода от одних вершин к другим.
Если дуги, связывающие вершины графа,— направленные (с технической точки зрения это означает, что если от вершины А можно перейти к вершине 5, то это не значит, что от вершины В можно обязательно непосредственно перейти к вершине А\ то даже для связного графа не всегда удается, выбрав некоторую вершину в качестве исходной, обойти его весь, проходя только по направлениям дуг. В этом случае часто поступают следующим образом. Выбирают некоторую вершину графа и обходят все его вершины, достижимые из выбранной. Если в графе остались еще непройденные вершины, то выбирают одну из таких вершин и снова обходят все вершины, достижимые из выбранной (разумеется, если в процессе обхода попадется одна из уже обойденных вершин, то не только ее, но и все, достижимые из нее вершины повторно рассматривать не надо). Процесс продолжается до тех пор, пока в графе не останется ни одной непройденной вершины. Если дуги в графе не направленные, то описанный алгоритм приведет к тому, что каждый раз после выбора начальной вершины будет пройдена одна компонента связности графа. Если граф — связный, то какую бы вершину ни выбрать в качестве начальной, все остальные будут из нее достижимы, так что никогда не потребуется после обхода всей компоненты связности производить еще один выбор вершины.
Наряду с обходами, при которых посещаются все вершины графа, можно также рассматривать обходы, предназначенные для прохождения всех дуг (ребер) графа. Такие обходы индуцируют некоторую нумерацию на множестве ребер подобно тому, как обходы вершин индуцируют нумерацию на множестве вершин. На практике обычно можно использовать для обходов дуг и вершин графа одни и те же алгоритмы. Действительно, практически все алгоритмы обхода графа хотя бы по одному разу обязательно исследуют как вершины, так и дуги графа. Для того чтобы понять, не находится ли на конце некоторой дуги еще не пройденная вершина, требуется исследовать эту дугу. И наоборот, если проходятся все дуги, значит, и все вершины будут пройдены, поскольку каждая вершина находится на конце некоторой дуги.
Мы будем рассматривать алгоритмы обхода, использующие представление графа, описанное в разд. 1.5 под названием i-графа, в котором для каждой вершины имеется список дуг, выходящих из этой вершины. Для алгоритмов обхода такое представление наиболее естественно, поскольку именно в этом
328
Гпава 6
случае проще всего переходить от вершины графа к соседним с нею вершинам. Действительно, зная номер некоторой вершины, мы легко сможем найти все смежные с ней вершины, исследуя выходящие из этой вершины дуги. В описании алгоритмов мы будем считать, что последовательно нумеруются вершины графа, но фактически теми же самыми алгоритмами нумеруются и дуги графа.
Представление в виде Z-графа описывает ориентированный граф, в котором все дуги имеют направление. Таким образом, если некоторая дуга связывает вершину А с вершиной В, то из этого еще не следует, что из вершины В можно пройти в вершину А. Может оказаться, что даже для связного графа не обязательно удастся пройти его весь, начав обход с произвольно выбранной вершины. Если граф— неориентированный, то его представление наряду с дугой, ведущей из вершины А в вершину 5, обязательно имеется также и дуга, ведущая из В в А. Это означает, что наши алгоритмы будут проходить каждое ребро графа дважды: один раз в направлении от А к В, г. другой раз — в обратном направлении.
Предыдущая << 1 .. 108 109 110 111 112 113 < 114 > 115 116 117 118 119 120 .. 161 >> Следующая
Книги
Web-программирован-
ие
Аппаратное обеспечение Графика Руководство по П.О. Самоучитель Теория программирования Фотошоп Языки программирования
Новые книги
Завалишин Д. "Интернетско-русский разговорник" (Web-программирование)

Заенцев И.В. "Нейронные сети: основные модели" (Web-программирование)

Владимиров А.А. "Wi-фу: «боевые» приемы взлома и защиты беспроводных сетей" (Web-программирование)

Вьейра Р. "SQL Server 2000. Программирование в 2 ч." (Web-программирование)

Веллинг Л.Т. "Разработка web приложений с помощью php и mysql" (Web-программирование)
Авторские права © 2013 ComputersBooks. Все права защищены.

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed