Основы объектно-ориентированного программирования задач на графах

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение высшего образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Инженерно-технологическая академия






В. А. ЛИТВИНЕНКО




ОСНОВЫ ОБЪЕКТНО-ОРИЕНТИРОВАННОГО ПРОГРАММИРОВАНИЯ ЗАДАЧ НА ГРАФАХ




Учебное пособие














Ростов-на-Дону - Таганрог
        Издательство Южного федерального университета
2019

УДК 004.438(075.8)
ББК 32.973
      Л641

Печатается по решению кафедры систем автоматизированного проектирования Института компьютерных технологий и информационной безопасности Южного федерального университета (протокол № 9 от 7 марта 2019 г.)


            Рецензенты:


доктор технических наук, профессор кафедры автоматизации производственных процессов Донского государственного технического университета (ДГТУ) Ю. О. Чернышев
кандидат технических наук, доцент кафедры ИБТС Института компьютерных технологий и информационной безопасности ЮФУ С. А. Ховансков


            Литвиненко, В. А.


Л641     Основы объектно-ориентированного программирования задач на
      графах : учебное пособие / В. А. Литвиненко ; Южный федеральный университет. - Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2019. - 133 с.

         ISBN 978-5-9275-3472-2
         Рассматриваются основы объектно-ориентированного программирования на С++ задач на графах - от создания класса до разработки иерархии классов, основанной на классификации способов задания графов.
         Пособие предназначено для студентов вузов, обучающихся по направлениям «Информатика и вычислительная техника» и «Информационные системы и технологии». Пособие может быть полезным для специалистов, занятых программированием алгоритмов решения задач на графах и сетях.
УДК 004.438(075.8)
ББК 32.973
ISBN 978-5-9275-3472-2
                                  © Южный федеральный университет, 2019
                                  © Литвиненко В. А., 2019
                                  © Оформление. Макет. Издательство Южного федерального университета, 2019

ОГЛАВЛЕНИЕ


ВВЕДЕНИЕ ....................................................... 6
1. УНИВЕРСАЛЬНОСТЬ ГРАФОВ ...................................... 9
Вопросы для самоконтроля ..................................... 131

2. ПРЕДСТАВЛЕНИЕ ГРАФОВ ....................................... 13
2.1. Матрица смежности ........................................ 13
2.2. Матрица инцидентности .................................... 13
2.3. Списочная форма........................................... 15
Вопросы для самоконтроля ...................................... 16

3. РАЗРАБОТКА КЛАССА ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ ... 17
3.1. Описание класса .......................................... 17
3.2. Объект класса ............................................ 18
3.3. Конструктор класса ....................................... 19
3.4. Деструктор класса ........................................ 21
3.5. Функции класса ........................................... 24
3.6. Ввод-вывод матрицы смежности графа ....................... 25
3.7. Определение вершин графа, смежных двум заданным вершинам . 27
3.8. Пример выполнения программы .............................. 29
3.9. Программа для работы с классом ........................... 30
Выводы ........................................................ 32
Вопросы для самоконтроля ...................................... 33

4. ПРОСТОЕ НАСЛЕДОВАНИЕ ПРИ РАЗРАБОТКЕ КЛАССОВ
ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ ................................... 35
4.1. Базовый и производный класс .............................. 35
4.2. Функция для проверки смежности двух вершин графа ......... 36

3

Оглавление

4.3. Вызов конструктора базового класса.........................37
4.4. Главная функция ...........................................37
4.5. Пример выполнения программы ...............................38
Вопросы для самоконтроля .......................................38

5. ПОЛИМОРФИЗМ ПРИ РАЗРАБОТКЕ КЛАССОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ ....................................40
5.1. Виртуальные функции .......................................40
5.2. Переопределение функций ...................................41
5.3. Вызов виртуальных функций .................................42
5.4. Пример выполнения программы ...............................43
Вопросы для самоконтроля .......................................44

6. ЗАДАЧИ НА ГРАФАХ И ПЕРЕГРУЗКА ОПЕРАЦИЙ ......................45
6.1. Функции-операции ..........................................45
6.2. Унарные функции-операции для ввода-вывода    графов .......46
6.3. Унарная функция-операция для проверки смежности двух вершин графа ..........................................................49
6.4. Перегрузка операций для виртуальных функций ...............52
6.5. Результат работы программы для унарных операций ...........54
6.6. Бинарные функции-операции .................................54
6.7. Бинарная функция-операция для определения вершин, смежных заданной вершине графа .........................................55
6.8. Бинарная функция-операция для объединения двух графов .....56
6.9. Пример выполнения программы для бинарных функций-операций .60
Вопросы для самоконтроля .......................................63

7. ИЕРАРХИИ КЛАССОВ ДЛЯ РЕШЕНИЯ ЗАДАЧ НА ГРАФАХ ................65
7.1. Структура и назначение классов ............................65

4

Оглавление

7.2. Абстрактные классы и чистые виртуальные функции .......... 67
7.3. Определение чистых виртуальных функций в классе Matr.......69
7.4. Определение чистых виртуальных функций в классе List...... 71
7.5. Главная функция .......................................... 76
7.6. Пример выполнения программы для иерархии классов ......... 77
Вопросы для самоконтроля ...................................... 79

8. ЗАДАЧИ НА ГРАФАХ ПОВЫШЕННОЙ СЛОЖНОСТИ ...................... 80
8.1. Иерархия и назначение функций классов .................... 80
8.2. Программирование функции определения паросочетания графа . 84
8.3. Программирование функции выделения семества клик, покрывающего все вершины графа ................................ 87
8.4. Структура главной функции в ООП .......................... 92

ЗАКЛЮЧЕНИЕ .................................................... 98
СПИСОК ЛИТЕРАТУРЫ.............................................. 99
ПРИЛОЖЕНИЯ ................................................... 100
Приложение 1 ................................................. 100
Приложение 2 ................................................. 102
Приложение 3 ................................................. 105
Приложение 4 ................................................. 109
Приложение 5 ................................................. 114
Приложение 6 ................................................. 120
Приложение 7 ................................................. 126

ВВЕДЕНИЕ

      Стандарт подготовки по направлениям «Информатика и вычислительная техника» и «Информационные системы и технологии» предусматривает освоение студентами технологий программирования. Технология объектно-ориентированного программирования является одной из наиболее распространенных технологий программирования на языках высокого уровня. Это связано, в первую очередь, с тем, что практически все современные информационные программные системы являются объектноориентированными. Одним из языков высокого уровня, который сохранил свои лидирующие позиции, является С++, что подтверждается постоянным развитием многоязыковой среды программирования MS Visual Studio для Windows, среды Embarcadero RAD Studio для Windows и Android, популярностью таких сред, как Xcode для платформы Apple, NetBeans для Windows, Mac и Linux, более простых, но популярных сред - CodeBlocks, CLion, Dev-C++, что является определяющим фактором для дальнейшего освоения и использования С++. Все это и определило выбор языка С++ как основного языка программирования для освоения студентами, обущающи-мися по направлениям «Информационные системы и технологии» и «Информатика и вычислительная техника», при изучении технологий программирования, в том числе объектно-ориентированного программирования.
      В качестве одного из объектов для освоения объектноориентированного программирования графы выбраны не случайно. Графы - это универсальная модель, которая широко используется при решении различных задач, имеющих практическое значение, например, в системах автоматизированного проектирования. Кроме того, задачи на графах являются хорошим практическим базисом для освоения программирования комбинаторно-логических алгоритмов.
      Пособие знакомит с основными понятиями теории графов, программированием задач на графах на С++ с использованием классов, перегрузки операций, виртуальных функций, абстрактных классов. Рассматривается объектно-ориентированное программирование задач на графах различного уровня сложности - от создания простого класса до разработки иерархии классов, основанной на классификации способов задания графов, таких как матрица смежности, матрица инцидентности, а также задание графов в

6

Введение

списочной форме. Программирование задач, рассмотренных в пособии, выполнено c использованием консольных приложений.
     Основная цель настоящего учебного пособия - показать процесс объектно-ориентированного программирования задач на графах как можно проще и сделать основной упор на использование различных структур данных, которые используются для программирования алгоритмов решения задач на графах, а также использования возможностей С++.
     В первом разделе пособия рассмотрены основные понятия теории графов, а также способы задания графов: табличный, списочный и графический. При этом в настоящем учебном пособии не ставится задача изучения теории графов. Этому вопросу посвящено достаточно большое число публикаций [1-5]. Кроме того, подробно с графами, их классификацией, а также с алгоритмами решения задач на графах студенты знакомятся в курсе «Дискретная математика».
     Во втором разделе рассматривается выбор структуры данных для программирования задач на графах, заданных матрицей смежности, матрицей инцидентности, а также для графов, представленных в списочной форме.
     В третьем разделе разрабатывается простой класс для решения задач на графах, рассматриваются основы построения классов, создание объектов класса, а также разработка функций для решения некоторых простых задач на графах, например, определения вершин графа смежных двум заданным вершинам.
     В четвертом и пятом разделах продолжена разработка классов для решения задач на графах. Рассмотрено простое наследование и использование виртуальных функций при решении задач на графах, использование конструкторов базовых и производных классов.
     Шестой раздел посвящен использованию перегрузки операций для создания унарных и бинарных операций для объектов классов, предназначенных для работы с графами.
     В седьмом разделе разрабатывается иерархия классов, основанная на классификации графов по способу их задания. Рассматриваются классы для работы с графами, заданными матрицей смежности и в списочной форме. При создании классов используются абстрактные классы и чистые виртуальные функции.

7

Введение

      В восьмом разделе рассматривается разработка приложения для решения более сложных задач теории графов, таких как определение паросо-четаний графа и выделения максимальных полных подграфов (клик) симметрических графов. Кроме того, рассмотрен подход к разработке программ на С++ с использованием функции класса, которая, по существу, выполняет роль главной функции.
      Для каждого раздела приведены контрольные вопросы для самопроверки. В приложениях приводятся тексты разрабатываемых в пособии программ.

1. УНИВЕРСАЛЬНОСТЬ ГРАФОВ



            1.1. Способы задания графа


     Граф - это универсальная абстрактная модель. Граф состоит из вершин и ребер. Вершины моделируют объекты, а ребра - отношения между двумя объектами.
     Рассмотрим следующий пример. Объекты - это студенты. Каждому студенту поставим в соответствие вершину графа. Сколько студентов, столько и вершин. Студенты могут дружить друг с другом или нет. «Дружба» - это отношение между студентами. Если два студента дружат, то между вершинами, которые им соответствуют, проведем ребро. Если два студента не дружат, то ребра нет.
     Граф можно задать графически, таблицей или списком. На рис. 1 показан граф для пяти студентов. Это графическое задание графа. Линии -это ребра, кружки - вершины. Если вершины соединены ребром, то говорят, что они смежны. На рис. 2 показано табличное представление этого графа - матрица смежности.


Рис. 1. Граф для пяти студентов

      Матрица смежности состоит из строк и столбцов. Если в графе пять вершин, то в матрице смежности будет пять строк и пять столбцов. Каждая строка и столбец имеет номер. Первая строка и первый столбец соответствуют вершине графа с номером «1» - первой вершине. Вторая строка и второй столбец соответствуют вершине графа с номером «2» - второй вершине, и т.д. Если на пересечении первой строки и второго столбца постав

9

1. Универсальность графов

лена «1», то это означает, что первая и вторая вершины соединены ребром.
Если стоит «0», то эти вершины ребром не соединены.


Рис. 2. Матрица смежности графа

      Граф отражает отношения между любыми парами вершин, т.е. бинарные отношения между объектами. В нашем примере объекты - это студенты, а отношение - «дружны два студента или нет». Граф (см. рис. 1) показывает, что Первый студент дружит только со Вторым, Второй студент дружит, кроме Первого, еще с Третьим и Пятым студентами, а Четвертый - не дружит ни с кем.
      Для того чтобы проверить дружат ли два студента, нужно узнать, есть ли ребро между вершинами графа, которые соответствуют этим студентам. По графическому изображению графа (см. рис. 1) это можно сделать визуально. По матрице смежности это можно узнать, проверив значение элемента на пересечении строки и столбца, которые соответствуют этим вершинам.
      Если требуется рассадить по партам наших студентов, то решить такую задачу можно, выделив в графе ребра, каждая пара которых имеет разные номера вершин. В нашем примере за одну парту можно посадить Первого и Второго студента, Пятого и Третьего. Четвертому студенту придется сидеть в гордом одиночестве. В теории графов эта задача называется задачей выделения в графе максимального паросочетания, т.е. такого паросоче-тания, количество ребер в котором наибольшее из всех возможных комбинаций.
      Паросочетание графа - это множество попарно непересекащихся между собой ребер графа.


10

Вопросы для самоконтроля


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



            Вопросы для самоконтроля


1. Что такое граф?
2. Какие два множества образуют граф?
3. Какие объекты могут моделировать вершины графа?
4. Какие отношения могут задавать ребра графа?
5. Чем отличается граф от мультиграфа?
6. Приведите пример объекта, который можно моделировать симметрическим графом.
7. Какая связь между понятием «отношение» и понятие ребра графа?
8. Приведите пример моделирования объекта мультиграфом.


11

1. Универсальность графов

9. Есть ли отличие между максимальным полным подграфом и кликой графа?
10. Может ли клика графа состоять из одной вершины?
11. Каким свойством должны обладать ребра паросочетания графа?
12. Как моделируется в матрице смежности петля у вершины графа?

2. ПРЕДСТАВЛЕНИЕ ГРАФОВ



            2.1. Матрица смежности


     Достаточно взглянуть на рисунок (см. рис. 2), чтобы понять, что матрицу смежности графа удобно представить двумерным массивом с одинаковым числом строк и столбцов. Массив может быть целого, символьного или логического типа. Выделить статическую память для матрицы смежности графа на пять вершин можно одним из следующих операторов:

                         int matr[5][5];
                         char matr[5][5];
                         bool matr[5][5];

     Массивом целых чисел представляют матрицу смежности с весами на ребрах, а также матрицу смежности мультиграфов.
     Мультиграф - это граф, любые пары вершин которого могут быть соединены несколькими ребрами.
     Символьным массивом задают матрицу смежности, если вес ребра не превышает 255, или матрицу смежности мультиграфа, любые две вершины которого могут быть соединены не более 255 ребер.
     Логическим массивом задают матрицу смежности графов, не имеющих весов ребер.
     Проверить, смежны или нет i-я и j-я вершины графа, можно так:

if (matr[i-1][j-1]) соии<"смежны”; else cout<<”He смежны”;


            2.2. Матрица инцидентности


     Кроме матрицы смежности для табличного задания графа используется также матрица инцидентности. Для графа (см. рис. 1) матрица инцидентности будет иметь вид (рис. 3).
     Матрица инцидентности имеет столько строк, сколько вершин в графе, а столбцов - сколько ребер. Элемент столбца будет равен 1, если вершина, которой соответствует строка, образует это ребро, и равен 0 для


13