Целью лабораторной работы является изучение основных структур данных, использующихся для хранения графов, и приобретение навыка разработки программ, преобразующих одни структуры в другие.
Требования к содержанию, оформлению и порядку выполнения
В содержательной части отчета по выполнению лабораторной работы требуется привести описание алгоритма, разработанного согласно своему варианту, и сделать вывод о преимуществах и недостатках использования различных СД для хранения графов. Алгоритмы рекомендуется оформлять с помощью блок-схем.
Теоретическая часть
Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.2.4.7 и 2.4.8.
Общая постановка задачи
Требуется разработать алгоритм преобразования исходной СД хранения графа в выходную СД. Варианты заданий представлены в таблице в следующем разделе.
В качестве дополнительного задания рекомендуется программно реализовать разработанный алгоритм.
Список индивидуальных данных
В таблице Л3.1 приведены варианты заданий. Каждая строка таблицы соответствует варианту. Например, в первом варианте требуется разработать алгоритм преобразования матрицы смежности графа в матрицу инцидентности, задающую тот же граф.
| Таблица Л3.1 | ||||||||||||
| Варианты заданий лабораторной работы №3 | ||||||||||||
| № варианта | Исходная СД | Выходная СД | ||||||||||
| матрица смежности | матрица инцидент-ности | массив ребер | массивы смежности | список ребер | списки смежности | матрица смежности | матрица инцидент-ности | массив ребер | массивы смежности | список ребер | списки смежности | |
| 1. | Ö | Ö | ||||||||||
| 2. | Ö | Ö | ||||||||||
| 3. | Ö | Ö | ||||||||||
| 4. | Ö | Ö | ||||||||||
| 5. | Ö | Ö | ||||||||||
| 6. | Ö | Ö | ||||||||||
| 7. | Ö | Ö | ||||||||||
| 8. | Ö | Ö | ||||||||||
| 9. | Ö | Ö | ||||||||||
| 10. | Ö | Ö | ||||||||||
| 11. | Ö | Ö | ||||||||||
| 12. | Ö | Ö | ||||||||||
| 13. | Ö | Ö | ||||||||||
| 14. | Ö | Ö | ||||||||||
| 15. | Ö | Ö | ||||||||||
| 16. | Ö | Ö | ||||||||||
| 17. | Ö | Ö | ||||||||||
| 18. | Ö | Ö | ||||||||||
| 19. | Ö | Ö | ||||||||||
| 20. | Ö | Ö | ||||||||||
| 21. | Ö | Ö | ||||||||||
| 22. | Ö | Ö | ||||||||||
| 23. | Ö | Ö | ||||||||||
| 24. | Ö | Ö | ||||||||||
| 25. | Ö | Ö | ||||||||||
| 26. | Ö | Ö | ||||||||||
| 27. | Ö | Ö | ||||||||||
| 28. | Ö | Ö | ||||||||||
| 29. | Ö | Ö | ||||||||||
| 30. | Ö | Ö |
Пример выполнения работы
Рассмотрим 30 вариант. В данном варианте исходный граф задается списками смежности. Требуется разработать алгоритм, преобразующий исходные списки смежности в список ребер, задающий тот же граф.
Для графа, представленного на рис.Л3.1, списки смежности представлены на рис.Л3.2. Такие списки являются входом алгоритма, который требуется разработать в данной лабораторной работе. Выходом алгоритма является список ребер. Для рассматриваемого графа список ребер представлен на рис.Л3.3.
 |
Алгоритм преобразования списков смежности в список ребер представлен блок-схемой на рис.Л3.4.
Контрольные вопросы к защите
1. Определение графа, ориентированного графа, взвешенного графа.
2. Определение цепи, цикла, контура.
3. Определение подграфа.
4. Определение дерева и покрывающего дерева.
5. Хранение графа с помощью матрицы смежности.
6. Хранение графа с помощью матрицы инцидентности.
7. Хранение графа с помощью массивов смежности.
8. Хранение графа с помощью массива ребер.
9. Хранение графа с помощью списков смежности.
10. Хранение графа с помощью списка ребер.
11. Хранение ориентированного дерева с помощью массива.
12. Проанализируйте преимущества и недостатки различных СД для хранения графов.
Способ оценки результатов
Критерии оценки результатов совпадают с критериями, определенными при описании лабораторной работы №1 в разделе «Способ оценки результатов».
Дата: 2016-09-30, просмотров: 314.
