(4 часа)
Цель работы: Освоить на практике основные структуры данных для хранения графовых моделей в вычислительной системе, так же базовые алгоритмы для обхода графа и задачи, базирующиеся на них
Домашнее задание:
1.Изучить структуры данных для представления ориентированных и неориентированных графов.
2.Изучить базовые алгоритмы обхода графов: поиск в ширину, поиск в глубину.
3.Разобраться в реализации задач построения каркасов в графе, построения каркаса минимального веса,нахождения циклов различной природы в графе.
4.Изучить алгоритм Дейкстры- нахождение кратчайших путей во взвешенном графе.
Порядок выполнения работы.
1.Открыть проект Delphi Structures.
2.Добавить в управляющее главное меню пункт «Лабораторная работа №9», при выборе которого должно появляться окно модуля «Graph» (модуль «Graph» с формой добавить в проект).
3.Установить на форму модуля Hesh компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №9.1.
4.В обработчике события onClick управляющей кнопки на языке
Object Pascal написать фрагмент программы для реализации алгоритма обработки графа в соответствии с вариантом задания.
5.Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.
6.произвести анализ запрограммированного алгоритма (по количеству сравнений).
7.Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.
Таблица 9.1
| № вар. | Текст задачи | |||
| 1. |
Дан связный неориентированный граф G=(V,E). (рис.1)
Граф задан с помощью матрицы смежности. Найти: используя алгоритм поиска в ширину, построить и вывести в объект на форму дерево поиска в ширину | |||
| 2. |
Дан связный неориентированный граф G=(V,E). (рис.2)
Граф задан с помощью матрицы смежности. Найти: используя алгоритм поиска в глубину, построить и вывести в объект на форму одиночный каркас(остовное дерево). | |||
| 3. |
Дан связный неориентированный граф G=(V,E). (рис.3)
Граф задан с помощью списков смежности. Найти: используя алгоритм поиска в глубину, построить и вывести в объект на форму одиночный каркас(остовное дерево). | |||
| 4. | Дан связный неориентированный граф G= (V, E).(рис.3) Найти все каркасы графа. | |||
| 5. |
Дан связный неориентированный граф G= (V, E).Ребра имеют вес w (рис.4) Граф описывается перечнем ребер с указанием их веса:
P:array[1..3,1..N*(N-1) div 2] of integer;
Найти каркас минимального веса, используя алгоритм Крускала.
| |||
| 6. | Дан связный неориентированный граф G= (V, E).Ребра имеют вес w (рис.4) Граф описывается матрицей смежности: P:array[1..N,1..N] of integer; Элемент матрицы не равный нулю,определяет вес ребра. Найти каркас минимального веса, используя алгоритм Прима. | |||
| 7. |
Дан ориентированный граф G=(V,E) с весовой функцией. Граф задан матрицей смежности.(рис.5)
Найти массив кратчайших расстояний от вершины с номером 0 до всех остальных вершин алгоритмом Дейкстры. | |||
| 8. | Пусть G=(V,E) - связный неориентированный граф. Точкой сочленения называется вершина, удаление которой делает граф несвязным.(На рис.6 точки сочленения закрашены.)
Используя алгоритм поиска в глубину, найти точки сочленения, если они есть, в графе G.
| |||
| 9. | Пусть G=(V,E) - связный неориентированный граф. Мостом графа G называется ребро, удаление которого делает граф несвязным. (На рис.6 мосты выделены.) Используя алгоритм поиска в глубину, найти мосты в графе G. |
Контрольные вопросы
1.Каковы особенности представления различных графов с помощью матрицы смежности?
2В чем преимущества и недостатки представления графов с помощью списков смежности?
3.В чем заключается методика раскраски вершин в алгоритме обхода графа поиском в ширину?
4.Что мы называем каркасом или остовом графа?
5.Что такое каркас минимального веса?
6.Что мы называем Эйлеровым циклом и какого условие его существования в графе?
7.Что такое Гамильтонов цикл?
8.Какова цель поиска алгоритмом Дейкстры?
