АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Алгоритм ОГВШ

Обходы графов

ЦЕЛЬ РАБОТЫ

4.1.1 Ознакомиться с теоретическими сведениями по теме «Обходы графов». Изучить алгоритмы обходов

4.1.2 Получить практические навыки по обходам графов.

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

4.2.1 Методические указания по выполнению практической работы.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

4.3.1 Изучить методические указания к практической работе.

4.3.2 Выполнить поиск графов в глубину.

4.3.3 Выполнить поиск графов в ширину.

СОДЕРЖАНИЕ ОТЧЕТА

4.4.1 Цель работы

4.4.2 Методические рекомендации

4.4.3 Порядок выполнения работы

4.4.4 Ответы на контрольные вопросы

4.4.5 Выводы

КОНТРОЛЬНЫЕ ВОПРОСЫ

4.5.1 Что такое граф?

4.5.2 Что такое вершины?

4.5.3 Что такое ребро?

4.5.4 Что представляет собой поиск в глубину?

4.5.5 Что представляет собой поиск в ширину?

ПРИЛОЖЕНИЕ 1

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ

ОБХОДЫ ГРАФОВ

Обход графа – это некоторое систематическое перечисление его вершин (и/или ребер). Наибольший интерес представляют обходы, использующие локальную информацию.

Среди всех обходов наиболее известны поиск в ширину (ОГВШ) и в глубину (ОГВГ). Алгоритмы поиска в ширину и в глубину лежат в основе многих конкретных алгоритмов на графах.

Ребра, не принадлежащие покрывающему дереву, называют хордами.

Алгоритм ОГВШ

Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины. Иначе говоря, сначала посещается начальная вершина, затем все вершины, смежные с ней, то есть находящиеся от нее на расстоянии 1, затем вершины, находящиеся от нее на расстоянии 2, и т.д.

При данном алгоритме рассматривается эффект «лесного пожара»

1. Вершина с максимальной степенью

2. строим дерево

3. рассматриваем остальные деревья, являющиеся вершинами графа, которые связаны с корнем дерева.

4. считаем, что дерево сгорело, но от него распространился пожар на другие деревья.

5. процесс «распространения пожара» распространяется до тех пор, пока не сгорят все деревья.

В несвязном графе процесс заканчивается после посещения всех узлов одной компоненты связности. Поэтому поиск в ширину можно использовать для проверки связности графа и выделения компонент связности.

Алгоритм ОГВГ:

По видимому, исследование графа (лабиринта) мифическим героем Тесеем с целью убийства Минотавра является первым успешным применением поиска с возвращениями на графах, называемого поиском в глубину.

Поиск в глубину - Идея этого метода - идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед.

Метод поиска в глубину известен под разными названиями, например, "бэктрекинг", "поиск с возвращением".

Для того чтобы выполнить поиск в глубину необходимо рассмотреть пути (кратчайшего) соединений между элементами.

1. Выбираем вершину, которая имеет максимальную степень

7(1) ->6(2) степень 2ойй вершины либо <, либо = степени 1ой вершины.

2. Путь должен быть таким, чтобы нельзя было возвратиться в вершину, рассмотренную ранее.

3. Процесс продолжается до тех пор, пока все вершины не будут пройдены.

Дата добавления: 2015-09-27 | Просмотры: 298 | Нарушение авторских прав