Содержание
Краткая постановка задания
Необходимо написать модуль, содержащий решения $11$ задач для работы с графами, и программу, демонстрирующую работу этого модуля. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязателен командно-текстовый интерфейс), либо иметь графический интерфейс пользователя.
Разобранные алгоритмы можно применять непосредственно, однако чаще всего они нуждаются в некоторых изменениях. При необходимости следует использовать вспомогательные функции.
В качестве данных, если не сказано иначе, рекомендуется брать заранее заготовленные текстовые файлы, содержащие описание подобранных графов. Случайная генерация графов неудобна, так как для многих алгоритмов нужны графы, обладающие заранее известными свойствами.
Граф хранится в текстовом файле (предпочтительнее) или вводится с клавиатуры, может быть задан любым из описанных выше способов. Необходимо иметь возможность прочитать его не только в соответствующую структуру, но и во все остальные. Желательно предусмотреть варианты хранения неориентированных и ориентированных графов.
Стоимость доработки программы
Ниже приведена стоимость доработки программы:
| № | Операция | Консольный формат | Визуальный формат |
| 1. | Построение матрицы смежности. | $150$ рублей | $300$ рублей |
| 2. | Построение матрицы инциденций. | $150$ рублей | $300$ рублей |
| 3. | Построение перечней ребер. | $180$ рублей | $300$ рублей |
| 4. | Построение списков связи. | $150$ рублей | $300$ рублей |
| 5. | Построение остовного дерева путем обхода в глубину. | $300$ рублей | $400$ рублей |
| 6. | Построение остовного дерева путем обхода в ширину. | $300$ рублей | $400$ рублей |
| 7. | Построение каркаса минимальной стоимости (алгоритм Краскала). | $600$ рублей | $800$ рублей |
| 8. | Построение каркаса минимальной стоимости (алгоритм Прима). | $600$ рублей | $800$ рублей |
| 9. | Поиск и построение Эйлеров цикла в графе. | $700$ рублей | $1\ 000$ рублей |
| 10. | Построение массива кратчайших путей алгоритмом Дейкстры. | $500$ рублей | $700$ рублей |
| 11. | Построение матрицы кратчайших путей алгоритмом Флойда. | $600$ рублей | $800$ рублей |
Данная работа предполагает написание программы на языке C++. При заказе нужных вам операций с графом вы получите качественно написанную и хорошо прокомментированную программу.
Дополнительно заказав алгоритм решения задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Варианты индивидуальных заданий и их стоимость реализации
ВАЖНО!
- Задания обладают неодинаковой сложностью. Есть достаточно нетривиальные операции, требующие кодирования дополнительных функций.
- Стоимость каждой операции обозначена в таблице ниже в самой правкой колонке «Стоимость».
| № | Формулировка задания | Стоимость |
| 1 | Найти самый длинный простой путь в графе (путь, все ребра которого попарно различны) | $600$ рублей |
| 2 | Найти медиану взвешенного графа, т е такую вершину, сумма расстояний от которой до всех других вершин минимальна. | $600$ рублей |
| 3 | Задана система односторонних дорог. Найти путь, соединяющий города $A$ и $B$ и не проходящий через заданное множество городов. | $500$ рублей |
| 4 | Определить, изоморфен ли заданный граф своему дополнению. | $800$ рублей |
| 5 | Мостом графа назовем такое ребро, удаление которого увеличивает число компонент связности графа. Найти все мосты для заданного графа. | $500$ рублей |
| 6 | Найти длину самого длинного простого пути от города $A$ до города $B$ в заданной системе односторонних дорог. | $500$ рублей |
| 7 | В заданном графе найти максимальный по количеству вершин полный подграф. | $800$ рублей |
| 8 | Задан ориентированный граф с $N$ ($1 \leq N \leq 10$) вершинами, пронумерованными целыми числами от $1$ до $N$. Напишите программу, которая подсчитывает количество различных путей между всеми парами вершин графа. | $600$ рублей |
| 9 | Необходимо добраться на самолете из города $A$ в город $B$ при условии, что между ними нет прямого авиационного сообщения, затратив при этом минимальные средства. Заданы возможные промежуточные аэропорты. Для каждой пары аэропортов известно, существует ли между ними прямой маршрут, и если да, то известна минимальная стоимость перелета по этому маршруту. | $600$ рублей |
| 10 | Даны два числа: $N$ и $M$. Построить граф из $N$ вершин и $M$ ребер. Каждой вершине ставится в соответствие число ребер, входящих в нее. Граф должен быть таким, чтобы сумма квадратов этих чисел была минимальна. | $700$ рублей |
| 11 | По заданной системе односторонних дорог определить, есть ли в ней город, куда можно попасть из любого другого города, проезжая не более $100$ км. | $500$ рублей |
| 12 | В графе найти максимальное (по количеству ребер) подмножество попарно несмежных ребер. | $700$ рублей |
| 13 | Определить, является ли заданный граф двудольным. | $800$ рублей |
| 14 | По системе двусторонних дорог определить, можно ли, построив какие-нибудь три новые дороги, из заданного города добраться до каждого из остальных городов, проезжая не более $100$ км. | $600$ рублей |
| 15 | Некоторые школы связаны компьютерной сетью. Между школами заключены соглашения: каждая школа имеет список школ-получателей, которым она рассылает программное обеспечение всякий раз, получив новое бесплатное программное обеспечение (извне сети или из другой школы). При этом, если школа $B$ есть в списке получателей школы $A$, то школа $A$ может не быть в списке получателей школы $B$. Требуется написать написать программу, определяющую минимальное количество школ, которым надо передать по экземпляру нового программного обеспечения, чтобы распространить его по всем школам сети в соответствии с соглашениями. | $800$ рублей |
| 16 | Известно, что заданный граф — не дерево. Проверить, можно ли из него получить дерево путем удаления $n$ вершин (каждая вершина удаляется вместе с инцидентными ей ребрами, $n$ вводится с клавиатуры). | $700$ рублей |
| 17 | Задан неориентированный граф. При прохождении по некоторым ребрам некоторые (определенные заранее) ребра могут исчезать или появляться. Найти кратчайший путь из вершины с номером $q$ в вершину с номером $w$. | $800$ рублей |
| 18 | Дан ориентированный граф с $N$ вершинами ($N \le 50$). Вершины и дуги окрашены в цвета с номерами от $1$ до $M$ ($M \leq 6$). Указаны две вершины, в которых находятся фишки игрока, и конечная вершина. Правила перемещения фишек:
Игра заканчивается, если одна из фишек достигает конечной вершины. Написать программу поиска кратчайшего пути до конечной вершины, если он существует. | $800$ рублей |
| 19 | Заданы два числа: $N$ и $M$ ($20 \leq M \leq N \leq 150$), где $N$ — количество точек на плоскости. Требуется построить дерево из $M$ точек так, чтобы оно было оптимальным. Дерево называется оптимальным, если сумма всех его ребер минимальна. Все ребра — расстояния между вершинами, заданными координатами точек на плоскости. | $700$ рублей |
| 20 | Треугольником в неориентированном графе называется тройка вершин, попарно соединенных дугами. Склеиванием треугольника называется операция замены вершин треугольника новой вершиной с сохранением всех связей с остальными вершинами графа. Дан неориентированный граф. Склейте все треугольники графа. | $700$ рублей |
| 21 | Проверить, является ли заданный ориентированный граф связным. | Бесплатно (см.пример ниже) |
Лабораторная работа $№4$ предполагает написание программы на языке C++. При заказе работы своего варианта вы получите качественно написанную и хорошо прокомментированную программу.
Дополнительно заказав алгоритм решения вашей задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Образец выполнения (вариант №21)
Условие задания
Проверить, является ли заданный ориентированный граф связным.
Алгоритм решения задачи
Прежде чем переходить непосредственно к кодированию данного задания, нужно провести его алгоритмизацию. Данный этап является обязательным и ни один профессиональный программист не опускает его в своей работе.
➡ Если граф является ориентированным, то можно говорить о нескольких вариантах его связности:
- Ориентированный граф называется сильно-связным, если в нем существует путь из произвольной вершины в любую другую произвольную вершину.
- Ориентированный граф называется слабо-связным, если является связным неориентированный граф, полученный из него заменой ориентированных ребер неориентированными.
Составители заданий ни слова не упомянули про данную тонкость, поэтому нам придется самим определиться, с каким типом связности работать.
💡 Очевидно, что будем анализировать ориентированный граф, который является сильно-связным.
Также будем считать, что анализируемый на связность граф является невзвешенным, то есть его дуги не обладают каким-либо весом. На вход программе будет подаваться текстовый файл (в формате *.txt), в котором хранится матрица смежности, описывающая структуру анализируемого ориентированного графа. В первой строке файла будет записано натуральное число, выражающее количество вершин рассматриваемого графа.
Пример входного текстового файла с данными и визуализация графа, построенного на основании этих данных:
➡ Является ли представленный выше ориентированный граф связным? Чтобы ответить на этот вопрос, нам нужно проверить необходимое и достаточное условие связности графа:
ориентированный граф будет связным, если существует путь из произвольной вершины в любую другую произвольную вершину.
Так как граф является ориентированным, то придется последовательно перебирать все его вершины! Потому что, если, например, мы смогли посетить вершину $№6$ из вершины $№5$, то это не гарантирует обратного.
Для обхода графа в основном применяются два классический алгоритма:
- Обход графа в ширину (в теории англ. BFS, Breadth-First-Searh).
- Обход графа в глубину (в теории англ. DFS, Depth-First-Search).
Студентам, которым предстоит сдача данной лабораторной работы, нужно в совершенстве понимать данные алгоритмы обхода.
Если у вас есть какие-то сложности с понимаем того, как устроены данные алгоритмы обхода графа, то можете записаться на частные занятия по программированию к репетитору
$\rightarrow$ Александру Георгиевичу (№тел.: $8(926) 610 — 61 — 95$).
Кстати, именно он является автором данной статьи, поэтому сможет ответить на любые вопросы, связанные с теорией графов.
➡ Алгоритм обхода графа в ширину задействует такую структуру данных, как очередь, а алгоритм обхода графа в глубину — стек. Возьмем за базу алгоритм DFS, использующий стек. Кстати, в лабораторной работе №2 были закодированы, как стек, так и очередь. Частично тем кодом можно воспользоваться при программировании данного задания. Но лишь частично!
Заданный граф состоит из $6$ вершин. Чтобы проверить ориентированный граф на связность, запустим последовательно алгоритм DFS (обход в глубину) из каждой его вершины.
Ниже приведены способы посещения всех вершин графа при первоначальной различной вершины графа. Посещения производятся в соответствии c алгоритмом DFS. Над каждой дугой графа проставлено число, которое показывает порядок перемещения между вершинами графа.
| № старт. вершины | Схема посещения вершин графа | Связность? |
| 1 |  |  |
| 2 |  | |
| 3 |  | |
| 4 |  | |
| 5 |  | |
| 6 |  | |
💡 Из какой бы вершины мы не начинали обход графа, всегда удается посетить абсолютно все вершины, то есть существует путь от произвольной вершины в любую другую произвольную, следовательно, заданный ориентированный граф является связным.
А теперь давайте из представленного графа удалим буквально одну связь/дугу между вершинами $№3$ и $№2$. И запустим алгоритм обхода DFS из вершины $№5$.
Как видите, результаты неутешительны, связность графа стала нарушена — он стал несвязным ориентированным графом! Теперь граф обладает больше одной компонентой связности. А достаточно было убрать всего лишь одну дугу…
В итоге, чтобы студент мог безболезненно правильно закодировать подобную задачу, он должен хорошо понимать:
- Принцип работы одномерных и двухмерных динамических массивов.
- Принцип работы динамической структуры данных стек.
- Принцип правильного конструирования программного обеспечения (разделение подзадач на отдельные функции).
- Принцип работы обхода графа в глубину (DFS).
- Как взаимодействовать с текстовыми файлами, используя файловые потоки.
Перечень пользовательских программных функций
Для решения поставленной задачи пришлось разработать следующие программные функции ($12$ штук):
| № | Смысл операции | Название функции в коде |
| 1. | Создание элемента стека. | TElem* CreateElem(const int pinf) |
| 2. | Добавление элемента в стек (в вершину стека). | void Push(const int pinf) |
| 3. | Получение значения элемента на вершине стека (не удаляя сам элемент). | int Peek(void) |
| 4. | Удаление элемента из вершины стека. | void Pop(void) |
| 5. | Выделение памяти под динамическую матрицу смежности графа. | int** CreateMatrix(const int psize) |
| 6. | Вывод матрицы смежности графа на экран. | void PrintMatrix(int** pmatrix, const int psize) |
| 7. | Заполнение матрицы смежности графа данными из заданного текстового файла. | int** ReadMatrixFromTextFile(const string pnameFile, int& psize) |
| 8. | Освобождение памяти из-под динамической матрицы смежности графа. | void DestroyMatrix(int** pmatrix, const int psize) |
| 9. | Обход неориентированного графа в глубину (с использованием структуры данных стек, нерекурсивный алгоритм). | bool DFS(int** pmatrix, const int psize, const int pstartVertex, bool pvisited[]) |
| 10. | Установка всем вершинам графа статуса «посещена / не посещена». | void SetStatusVertex(bool pvisited[], const int psize, const bool pstatus) |
| 11. | Проверка ориентированного графа на связность. | void IsConnectedGraph(int** pmatrix, const int psize) |
| 12. | Главная функция программы (точка входа). | int main(void) |
Реализация задачи на языке С++
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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 | #include <iostream> // для ввода, вывода данных #include <iomanip> // для форматного вывода информации #include <string> // для работы со строками #include <fstream> // для работы с файлами #include <Windows.h> // для заголовка консольного окна using namespace std; // подключаем стандартное пространство имен //--------------------------------------------------------------------------- // структура "Элемент стека" //--------------------------------------------------------------------------- struct TElem { int inf; // значение информационного поля элемента TElem* next; // ссылка на следующий элемент стека } *top = NULL; // глобальный указатель на вершину стека //--------------------------------------------------------------------------- // создание элемента стека //--------------------------------------------------------------------------- TElem* CreateElem(const int pinf) { TElem* add = new TElem; add->inf = pinf; add->next = NULL; return add; } //--------------------------------------------------------------------------- // добавление элемента в вершиу стека //--------------------------------------------------------------------------- void Push(const int pinf) { TElem* add = CreateElem(pinf); if(top != NULL) add->next = top; top = add; } //--------------------------------------------------------------------------- // получение значения элемента на вершине стека //--------------------------------------------------------------------------- int Peek(void) { return (top->inf); } //--------------------------------------------------------------------------- // удаление элемента из вершины стека //--------------------------------------------------------------------------- void Pop(void) { TElem* del = top; top = top -> next; del = NULL; } //--------------------------------------------------------------------------- // выделение памяти под матрицу смежности графа //--------------------------------------------------------------------------- int** CreateMatrix(const int psize) { int** matrix = new int*[psize]; for(int i = 0; i < psize; i++) matrix[i] = new int[psize]; return matrix; } //--------------------------------------------------------------------------- // вывод матрицы смежности графа на экран //--------------------------------------------------------------------------- void PrintMatrix(int** pmatrix, const int psize) { cout << endl << "Матрица смежности заданного графа имеет вид: " << endl; for(int i = 0; i < psize; i++) { for(int j = 0; j < psize; j++) cout << setw(8) << pmatrix[i][j]; cout << endl << endl; } } //--------------------------------------------------------------------------- // заполнение матрицы смежности графа данными из текстового файла //--------------------------------------------------------------------------- int** ReadMatrixFromTextFile(const string pnameFile, int& psize) { ifstream file(pnameFile); file >> psize; int** matrix = CreateMatrix(psize); for(int i = 0; i < psize; i++) for(int j = 0; j < psize; j++) file >> matrix[i][j]; file.close(); return matrix; } //--------------------------------------------------------------------------- // освобождение памяти из-под матрицы смежности графа //--------------------------------------------------------------------------- void DestroyMatrix(int** pmatrix, const int psize) { for(int i = 0; i < psize; i++) delete []pmatrix[i]; delete []pmatrix; } //--------------------------------------------------------------------------- // обход графа в глубину (с использованием стека, нерекурсивный вариант) // false - не все вершины были посещены // true - все вершины были посещены //--------------------------------------------------------------------------- bool DFS(int** pmatrix, const int psize, const int pstartVertex, bool pvisited[]) { // стек вершин изначально пуст top = NULL; // помещаем в стек стартовую вершину (нумерация вершин с 0) Push(pstartVertex - 1); // помечаем стартовую вершину, как посещенную pvisited[pstartVertex - 1] = true; // пока стек не станет пустым while(top != NULL) { // берем вершину, находящуюся на вершине стека int numberCurrentVertex = Peek(); // удаляем вершину из стека Pop(); // последовательно добавляем в стек все вершины, которые смежны // только что взятой вершины из стека + только те вершины, которые не посещены for(int j = 0; j < psize; j++) if((pmatrix[numberCurrentVertex][j] == 1) && (pvisited[j] == false)) { Push(j); // добавляем еще непосещенную вершину в стек pvisited[j] = true; // устанавливаем статус этой вершины, как "посещена" } } // проверка статуса вершины графа на посещенность for(int i = 0; i < psize; i++) if(pvisited[i] == false) return false; return true; } //--------------------------------------------------------------------------- // установка всем вершинам графа статуса "посещена/не посещена" // false - не посещена // true - посещена //--------------------------------------------------------------------------- void SetStatusVertex(bool pvisited[], const int psize, const bool pstatus) { for(int i = 0; i < psize; i++) pvisited[i] = pstatus; } //--------------------------------------------------------------------------- // проверка ориентированного графа на связность (ключевая функция программы) //--------------------------------------------------------------------------- void IsConnectedGraph(int** pmatrix, const int psize) { // отвечает за статус вершины "посещена/не посещена" bool* visited = new bool[psize]; // запускаем обход графа в глубину ИЗ КАЖДОЙ вершины for(int i = 1; i <= psize; i++) { SetStatusVertex(visited, psize, false); bool isVisitedAllVertexes = DFS(pmatrix, psize, i, visited); // обход графа в глубину с вершины №i // если при обходе графа в глубину не все вершины были посещены, значит он несвязный if(isVisitedAllVertexes == false) { cout << endl << "Заданный ориентированный граф является НЕСВЯЗНЫМ!" << endl; cout << "Из вершины №" << i << " нельзя добраться до любой вершины графа." << endl; return; } } cout << endl << "Заданный ориентированный граф является СВЯЗНЫМ!" << endl; } //--------------------------------------------------------------------------- // главная функция программы (точка входа) //--------------------------------------------------------------------------- int main(void) { setlocale(LC_ALL, "rus"); // настройка руссификации диалогов программы // настройка заголовка консольного окна static const TCHAR* title = TEXT("Практикум на ЭВМ. Структуры данных и алгоритмы. С++. Лабораторная работа №4 (графы)"); SetConsoleTitle(title); int size; // размер матрицы смежности графа (количество вершин графа) int** matrix = NULL; // динамическая матрица смежности графа string nameInputTextFile; // имя входного текстового файла с данными (матрица смежности) // запрашиваем с клавиатуры имя входного текствого файла cout << "Введите имя текстового файла с данными: "; getline(cin, nameInputTextFile); ifstream textFile(nameInputTextFile); textFile.close(); if(!textFile) // если файла с введенным именем НЕ существует, то выдаем сообщение и завершаем работу программы cout << endl << "Файла с именем \'" << nameInputTextFile << "\' не существует! Чтение матрицы смежности графа невозможно!"; else { // читаем матрицу смежности графа из текстового файла matrix = ReadMatrixFromTextFile(nameInputTextFile, size); // выводим считанную матрицу смежности графа на экран PrintMatrix(matrix, size); // проверка графа на связность IsConnectedGraph(matrix, size); // удаляем память из-под динамической матрицы смежности графа DestroyMatrix(matrix, size); matrix = NULL; // чтобы не было висячей ссылки } cout << endl << "Для завершения работы программы нажмите клавишу ENTER..."; fflush(stdin); cin.get(); // задержка работы программы, чтобы можно было просмотреть результаты return 0; // завершение работы программы и передача управления в ОС } //--------------------------------------------------------------------------- |
Результаты работы программы
| № | Граф | Результат |
| 1 |  |  |
| 2 |  |  |
| 3 |  |  |
2 комментария