Пример выполнения работы

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

Для графа, представленного на рис.Л6.1, списки смежности представлены на рис.Л6.2. Такие списки являются входом алгоритма, который требуется разработать в данной лабораторной работе. Выходом алгоритма является список ребер. Для рассматриваемого графа список ребер представлен на рис.Л6.3.

Алгоритм преобразования списков смежности в список ребер представлен блок-схемой на рис.Л6.4.

Контрольные вопросы к защите

1. Определение графа, ориентированного графа, взвешенного графа.

2. Определение цепи, цикла, контура.

3. Определение подграфа.

4. Определение дерева и покрывающего дерева.

5. Хранение графа с помощью матрицы смежности.

6. Хранение графа с помощью матрицы инцидентности.

7. Хранение графа с помощью массивов смежности.

8. Хранение графа с помощью массива ребер.

9. Хранение графа с помощью списков смежности.

10. Хранение графа с помощью списка ребер.

11. Хранение ориентированного дерева с помощью массива.

12. Проанализируйте преимущества и недостатки различных СД для хранения графов.

Также к защите лабораторной работы №6 следует подготовить вопросы для повторения темы 7,8.

Способ оценки результатов

Критерии оценки результатов лабораторной работы №6 не отличаются от критериев оценки результатов лабораторной работы №1.