Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
2018-01-03 | 267 |
5.00
из
|
Заказать работу |
|
|
Итерация | Номер текущей элемента файла | Элемент, записываемый в файл F3 | |
F1 | F2 | ||
i | j | ||
F31=F11=1 | |||
F32=F12=2 | |||
F33=F21=3 | |||
F34=F22=4 | |||
F35=F13=5 | |||
F36=F14=7 | |||
F37=F23=8 | |||
F38=F24=8 | |||
F39=F25=10 | |||
F310=F15=11 | |||
F311=F16=12 | |||
F312=F26=15 | |||
F313=F17=16 | |||
F314=F27=17 | |||
* | F315=F18=20 |
Поиск на графах
На практике часто возникают задачи, связанные с прохождением по вершинам графа. Например, необходимо ответить на вопрос: достижима ли вершина d из вершины r? То есть, существует ли путь из вершины r в вершину d.
Для ответа на вопрос, достижима вершина d из вершины r или нет, необходимо организовать обход вершин графа, начиная из вершины r. Если во время обхода мы встретим вершину d, следовательно, вершина d достижима из вершины r, в противном случае - d из r не достижима.
Существует два способа организации обхода: поиск в глубину и поиск в ширину.
Поиск в глубину
Поиск в глубину на графе G=(V,E) осуществляется по следующим правилам:
1. Начинаем поиск с начальной вершины r. В качестве текущей вершины v берем вершину r.
2. Из текущей вершины v двигаемся в любую, ранее не пройденную вершину w, если такая вершина найдется (если вершины w нет, см. пункт 3). Запоминаем дугу, по которой мы попали в вершину w. В качестве текущей вершины v берем вершину w.
3. Если из вершины v мы не можем попасть в ранее не пройденную вершину w, то возвращаемся в вершину x, из которой мы попали в v. В качестве текущей вершины v берем вершину x.
4. Процесс поиска (пункты 2, 3) заканчивается, когда мы пытаемся вернуться назад из вершины, с которой начался поиск (вершина r).
|
Поиск в глубину проиллюстрирован на рис. 7.15.
Алгоритм поиска в глубину представлен укрупненной блок-схемой на рис.7.16.
В алгоритме поиска в глубину требуется определять номер неокрашенной вершины (k) смежной вершине v (см. рис.7.16). Данные действия проще всего реализовать, когда исходный граф хранится матрицей смежности или упакованной матрицей смежности.
В алгоритме используются операции со стеком. Реализация стека может быть любой: на массиве, с помощью указателей или курсоров. Наиболее рационально реализовать стек на массиве. Это связано с тем, что максимальная глубина стека не может превышать числа вершин графа.
Для окраски вершин графа (см. рис.7.16, оператор «Окрасить вершину K») следует использовать множество. В данное множество заносятся окрашенные вершины. Если в алгоритмическом языке стандартный тип «множество» отсутствует, то для реализации множества можно использовать массив M длины n, где n - число элементов множества. Элементами массива M являются числа 0 и 1, причем, M[i]=0, если i-ый элемент принадлежит множеству и M[i]=1, если i-ый элемент не принадлежит множеству. В этом случае оператор «Окрасить вершину K» реализуется следующим образом: M[K]:=1.
Отметим, что дуги, по которым осуществляется обход графа (окрашенные дуги) в результате выполнения алгоритма поиска, образуют ориентированное дерево с корнем в начальной вершине. Поэтому для окраски дуги графа (см. рис.7.16, оператор «Окрасить дугу (v,K)») следует использовать массив P, хранящий ориентированное дерево (см. разд. 2.4.8). В этом случае оператор «Окрасить дугу (v,K)» реализуется следующим образом: P[K]:=v.
Поиск в ширину
При поиске в ширину порядок исследования дуг графа отличается. Поиск в ширину производится следующим образом:
1. Начинаем поиск с произвольной вершины r. Формируем множество текущих вершин A, включив в него вершину r.
2. Идем в ранее не пройденные вершины по всем дугам, имеющим начальную вершину, принадлежащую множеству A. Запоминаем эти дуги. Формируем множество A, включив в него конечные вершины пройденных дуг.
|
3. Процесс поиска (пункт 2) заканчивается, когда множество A станет пустым.
Поиск в ширину проиллюстрирован на рис. 7.17.
Для организации хранения множества A удобно использовать очередь. Алгоритм поиска в ширину представлен укрупненной блок-схемой на рис.7.18.
В алгоритме поиска в ширину используются те же структуры данных, что и в алгоритме поиска в глубину, за исключением того, что стек заменен очередью.
Реализация очереди может быть любой: на циклическом массиве, с помощью указателей или курсоров. Поскольку максимальная глубина очереди не может превышать числа вершин графа, то наиболее рационально реализовать очередь на циклическом массиве.
|
|
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Автоматическое растормаживание колес: Тормозные устройства колес предназначены для уменьшения длины пробега и улучшения маневрирования ВС при...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!