«Алгоритм нахождения стягивающего дерева методом поиска в глубину» - Курсовая работа

05.11.2023
20
2484

Содержание

Введение

Заключение

Список литературы

Примечания

Автор: navip

Содержание

АЛГОРИТМ НАХОЖДЕНИЯ СТЯГИВАЮЩЕГО ДЕРЕВА МЕТОДОМ ПОИСКА В ГЛУБИНУ

Введение

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

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

Тема исследования: Алгоритм нахождения стягивающего дерева методом поиска в глубину.

Объект исследования – ориентированные графы и деревья.

Предмет исследования – нахождение стягивающего дерева методом поиска в глубину.

Цель работы: Разработка программы на языке Turbo Pascal алгоритма нахождения стягивающего дерева методом поиска в глубину.

Для достижения этой цели были поставлены следующие задачи:

 обзор литературных данных по теме исследования дипломной работы;

 дать теоретическое обоснование алгоритма нахождения стягивающего дерева методом поиска в глубину;

 провести в ручную анализ графа и найти стягивающее дерево;

 составить программу для каждой задачи, реализующий алгоритм нахождения стягивающего дерева методом поиска в глубину;

 сравнить ручной анализ графа и результаты алгоритма нахождения стягивающего дерева методом поиска в глубину.

Заключение

В работе был реализован алгоритм нахождения стягивающего дерева методом поиска в глубину. По данному алгоритму была составлена программа, работа которой была продемонстрирована.

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

Анализ алгоритмов обхода

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

Рассуждение справедливо и для обхода в глубину. В этом случае мы заходим вглубь графа пока не наткнемся на тупик. Посетим ли мы, возвращаясь, все остальные узлы? Может ли так получиться, что в какую-то из вершин графа мы не зайдем? При каждом попадании в тупик мы возвращаемся до первого узла, из которого есть проход к еще не посещенному узлу. Тогда мы следуем этим проходом и снова идем по графу в глубину. Встретив новый тупик, мы вновь возвращаемся назад, пока не наткнемся на первую вершину с еще не посещенным соседом. Чтобы одна из вершин графа осталась непосещенной, нужно, чтобы она не была соседней ни для одной из посещенных вершин. А это и означает, что граф несвязен вопреки наши предположениям. При обходе в глубину мы также должны посетить все узлы.

Что можно сказать про эффективность такого алгоритма? Будем предполагать, что основная часть всей работы приходится на посещение узла. Тогда расходы на проверку того, посещали ли мы уже данный узел, и на переход по ребру можно не учитывать. Поэтому порядок сложности алгоритма определяется числом посещений узлов. Как мы уже говорили, каждая вершина посещается в точности один раз, поэтому на графе с N вершинами происходит N посещений. Таким образом, сложность алгоритма равна O(N)

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

Таким образом, развитие информационных технологий, их проникновение во все области жизнедеятельности человека требуют компьютерного отображения информации в виде соответствующих структур данных. И графы, являясь одной из частей этих структур данных, играют важную роль в современном программировании, графы встречаются в сотнях разных задач.

Список литературы

1. Hефедов В.H., Осипова В.А. Куpс дискpетной математики. - М.: МАИ, 1992, 264 с.

2. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы.-М.:Наука,1975.

3. Белов Теория Графов, Москва, «Наука»,1968.

4. Берж К. Теория графов и ее применение. - М.: ИЛ, 1962.

5. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990.

6. Зыков А. А. Теория конечных графов.-Новосибирск:Наука; Сиб. отд-ние, 1969.

7. Йенсен П., Барнес Д. Потоковое программирование.-М.:Радио и связь,1984.

8. Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.

9. Кофман А. Введение в прикладную комбинаторику.-М.:Наука,1975.

10. Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978.

11. Кузнецов О.П. Дискретная математика для инженера, 3-е изд., перераб. и доп. – СПб: Издательство «Лань», 2004.

12. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.

13. Липский В. Комбинаторика для программистов.-М.:Мир, 1988.

14. Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир,1981.

15. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях.-Новосибирск: Наука; Сиб. отд-ние, 1990.

16. Окулов С.М.Конспекты занятий по информатике (алгоритмы на графах). Учебное пособие для студентов и учителей школ. - Киров, 1996.

17. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.-М.:Мир,1985.

18. Романовский И.В. Алгоpитмы pешения экстpемальных задач. - М.: Hаука, 1977, 352 с.

19. Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.:Мир,1984.

20. Смольяков Э.Р. Введение в теоpию гpафов. М.: МГТУ, 1992, 32 с.

21. Филипс Д., Гарсиа-Диас А. Методы анализа сетей. - М.: Мир, 1984.

22. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях.-М.:Мир,1963.

23. Фрэнк Г., Фриш И. Сети, связь и потоки.-М.:Связь,1978.

24. Харари Ф. Теория графов.-М.:Мир,1973.

25. Ху Т. Целочисленное программирование и потоки в сетях.- М.:Мир,1974.

Примечания

К работе прилагается программа с исходным кодом.

К работе прилагается все исходники.

К работе прилагается рабочая программа на языке программирования.

	Тема:	«Алгоритм нахождения стягивающего дерева методом поиска в глубину»
	Раздел:	Информатика
	Тип:	Курсовая работа
	Страниц:	20
	Стоимость текста работы:	970 руб.

Нужна похожая работа?
Закажите авторскую работу по вашему заданию.

Цены ниже рыночных
Необходимый уровень антиплагиата
Прямое общение с исполнителем вашей работы
Бесплатные доработки и консультации
Минимальные сроки выполнения
Пишем сами, без нейросетей

Мы уже помогли 24535 студентам

Средний балл наших работ

4.89 из 5

Узнайте стоимость
написания вашей работы

Предыдущая работа

Разработка интеллектуальной информационной системы экономического анализа деятельности предприятия

Следующая работа

Автоматизация рабочего места (АРМ) менеджера