Целью лабораторной работы является изучение основных структур данных, использующихся для хранения графов, и приобретение навыка разработки программ, преобразующих одни структуры в другие.
Требования к содержанию, оформлению и порядку выполнения
В содержательной части отчета по выполнению лабораторной работы требуется привести описание алгоритма, разработанного согласно своему варианту, и сделать вывод о преимуществах и недостатках использования различных СД для хранения графов. Алгоритмы рекомендуется оформлять с помощью блок-схем.
Теоретическая часть
Теоретические сведения, необходимые для выполнения лабораторной работы, представлены в разд.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, просмотров: 258.