3. Порядок выполнения работы

5. Получить вариант задания у преподавателя.

6. Разработать программу.

7. Продемонстрировать выполнение программы преподавателю, сравнить полученный результат с ожидаемым.

8. Оформить и защитить отчет.

4. Требования к оформлению отчета

Отчет по лабораторной работе должен содержать следующие разделы:

• задание по лабораторной работе;

• листинг программы;

• выводы по проделанной работе.

5. Варианты заданий

1. Реализовать алгоритм сортировки включением.

2. Реализовать алгоритм обменной сортировки.

3. Реализовать алгоритм сортировки выбором.

4. Реализовать сортировку разделением.

6. Контрольные вопросы.

1. Что такое сортировка? Приведите примеры использования.

2. Какие алгоритмы сортировки Вам известны?

3. Как оценивается сложность сортировки?

Лабораторная работа №6 способы задания графов

1. Цель работы

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

2. Теоретические сведения

Неориентированным графом или просто графом называется комбинаторный объект, состоящий из двух конечных множеств G (X, U), где Х – множество вершин графа, а U – множество неупорядоченных пар элементов из Х, называемых ребрами графа.

Ориентированный граф G (Х, U) отличается от неориентированного тем, что элементы множества дуг Х упорядочены, что задает направление каждой дуги.

Пусть u=(x, y) – дуга ориентированного графа G. Вершина x называется началом дуги u, а вершина y – концом дуги u.

Граф является симметричным, если существование любой дуги вида (x, y) влечет за собой существование дуги вида (y, x).

Известны следующие основные способы задания графов.

Задание графов с помощью матрицы смежности.

Это один из самых распространенных методов задания графов.

Матрицей смежности называется квадратная матрица А = (a_ij), i=1…n, j=1…n, размером (nxn), значение каждого элемента которой определяется следующий образом

С помощью матрицы смежности удобно описывать алгоритмы на графах. Одним из достоинств этого методы является компактное представление для графов с большим числом дуг. К недостаткам следует отнести большой расход памяти при работе с графами, имеющими небольшое число дуг (матрица смежности при этом получается весьма разреженной). Матрица смежности неориентированного графа сим­метрична относительно главной диагонали, поэтому до­статочно хранить в памяти только ее половину относительно главной диагонали. Зада­ние графа с помощью матрицы смежности удобно еще и тогда, когда граф взвешенный и элементами матри­цы являются не нули и единицы, а веса дуг. Пример задания ориентированного и неориентированного гра­фов матрицами смежности приведен на рис.1.

A (G₁) =

A (G₂) =

G₁ – ориентированный граф

G₂ – неориентированный граф

Рис.1. Представление графов с помощью матрицы смежности.

Как было сказано, используя матрицу смежности можно задавать взвешенный граф, если заменить 0 и 1 на веса дуг. На рис.2. изображен пример таких матриц (x_i – веса дуг).

G₁ = , G₂ =

G₁ – ориентированный граф

G₂ – неориентированный граф

Рис.2. Представление графов с помощью матриц, элементами которых являются веса дуг

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

Одной из альтернатив рассмотренного метода явля­ется представление графов с помощью списка смежности.

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

Имя – имя вершины.

К – количество дуг, исходящих из этой вершины.

Весi – вес i-й дуги i=1…K (в случае взвешенного графа).

Указательi – указатель на i-ю вершину, i=1…K.

Граф представляется с помощью |Х| списков смежности, по одному для каждой вершины. Если чис­ло дуг в ориентированном графе мало по сравнению с полным графом, то этот способ представления эффективнее, чем представление с помощью матрицы смежности. Списки смежности легко реализуются с помощью списоч­ных структур. Менее удобен этот способ представления для за­дания взвешенных графов, так как тогда требуется выделение дополнительной памяти для хранения весов дуг.

Задание графов с помощью списка дуг.

Этот метод применяется в тех случаях, когда необходимо иметь отдельную, не­зависимую нумерацию дуг. При этом способе каждой дуге сопоставляется тройка <u, х, у>, где и — имя дуги, х — ее начало, у — ее конец. Этот способ представле­ния легко обобщается на случай взвешенных графов, путем добавления элемента, определяющего вес дуги.

Данный способ представления может задаваться в виде двумерного массива, где первое измерение – номер дуги, второе – ее параметры.