17_Лабораторная_4
.docxСанкт-Петербургский государственный
электротехнический университет «ЛЭТИ» им. В.И. Ульянова (Ленина) (СПбГЭТУ)
Факультет компьютерных технологий и информатики
Кафедра ВТ
Пояснительная записка к курсовой работе
на тему:
«Графы»
по дисциплине «Алгоритмы и структуры данных»
Вариант 17
Выполнил: студент гр. 8091 Гришин И.Д. ___________
Проверил: старший преподаватель Колинько П.Г. ___________
Санкт-Петербург
2020
Содержание
Техническое задание 3
2. Формализация задания 3
3. Контрольные тесты 4
4. Временная сложность 5
5. Результаты измерения времени 5
Выводы 6 Список используемой литературы 7
Приложение 1 8
Цель работы
Получить практические навыки работы с графами на языке программирования C++.
Задание
Реализовать алгоритм проверки наличия цикла отрицательной стоимости в ориентированном графе с нагруженными рёбрами.
3. Способ представления данных в памяти
Для решения задачи был выбран алгоритм Беллмана—Форда, в отличие от многих других графовых алгоритмов, более удобно представлять граф в виде одного списка всех рёбер (а не n списков рёбер — рёбер из каждой вершины). В приведённой реализации заводится структура данных Edge для ребра. Входными данными для алгоритма являются числа V, E список E рёбер, и номер стартовой вершины V.
4. Описание алгоритма Беллмана—Форда
Входные данные: Граф и начальная вершина src. Выходные данные: Кратчайшее расстояние до всех вершин от src. Если попадается цикл отрицательного веса, то самые короткие расстояния не вычисляются, выводится сообщение о наличии такого цикла.
На этом шаге инициализируются расстояния от исходной вершины до всех остальных вершин, как бесконечные, а расстояние до самого src принимается равным 0. Создается массив dist[] размера |V| со всеми значениями равными бесконечности, за исключением элемента dist[src], где src — исходная вершина.
Вторым шагом вычисляются самые короткие расстояния. Следующие шаги нужно выполнять |V|-1 раз, где |V| — число вершин в данном графе.
Произведите следующее действие для каждого ребра u-v: Если dist[v] > dist[u] + вес ребра uv, то обновите dist[v] dist [v] = dist [u] + вес ребра uv
На этом шаге сообщается, присутствует ли в графе цикл отрицательного веса. Для каждого ребра u-v необходимо выполнить следующее:
Если dist[v] > dist[u] + вес ребра uv, то в графе присутствует цикл отрицательного веса.
Идея шага 3 заключается в том, что шаг 2 гарантирует кратчайшее расстояние, если граф не содержит цикла отрицательного веса. Если мы снова переберем все ребра и получим более короткий путь для любой из вершин, это будет сигналом присутствия цикла отрицательного веса.
5. Контрольные тесты
Рис 1. Проведение тестов в программе «Графы»
Рис 2. Проведение тестов в программе «Графы»
Рис 3. Проведение тестов в программе «Графы»
Рис 4. Проведение тестов в программе «Графы»
Рис 5. Проведение тестов в программе «Графы»
5. Временная сложность
Функция |
Ожидаемая |
Создание |
O(VE) |
Обход |
O(VE) |
Вывод |
O(VE) |
6. Выводы
При выполнении курсовой работы были получены практические навыки работы с графами на языке программирования «С++». Также для работы программы был использован алгоритм Беллмана—Форда в ориентированном весовом графе. Временная сложность обработки алгоритма совпала с ожидаемой и равна O(VE).
7. Список используемой литературы
1. Колинько П. Г. Алгоритмы и структуры данных. Часть 1: Пособие к самостоятельной работе и курсовому проектированию. Вып. 2003 (для заочников). –– СПб., 2020. — Error: Reference source not found с.
2. Хабрахабр [Электронный ресурс] /. — Электрон. текстовые дан. — Режим доступа: https://habr.com/ru/company/otus/blog/484382/, свободный
3. Сайт MAXimal. Проверка графа на ацикличность и нахождение цикла. Электронный источник. http://e-maxx.ru/algo/finding_cycle
8. Приложение
#include <iostream> // Проверка наличия цикла отрицательной стоимости в ориентированном графе с нагруженными рёбрами using namespace std; // Cтруктура для представления взвешенного ребра в графе struct Edge { int src, dest, weight; }; // Cтруктура для представления связного, направленного и взвешенного графа struct Graph { int V, E; // V → Количество вершин, E → Количество ребер struct Edge *edge; // Граф представлен в виде массива ребер }; // Создаем граф с V вершинами и E ребрами Graph* createGraph(int V, int E) { Graph* graph = new Graph; graph->V = V; graph->E = E; graph->edge = new Edge[graph->E]; return graph; } Graph* generateGraph(Graph* graph, int V, int E) { Graph* temp = graph; srand(static_cast<unsigned int>(time(nullptr))); for (int i = 0; i < E; i++) { temp->edge[i].src = i; temp->edge[i].dest = rand()%E; temp->edge[i].weight = rand() % 20 - 10; } return temp; } // Основная функция, которая находит // кратчайшие расстояния от src до всех других вершин, // используя алгоритм Беллмана-Форда. // Функция также обнаруживает отрицательный весовой цикл bool isNegCycleBellmanFord(struct Graph *graph, int src) { int V = graph->V; int E = graph->E; int dist[V]; // Шаг 1: Инициализировать расстояния от src // до всех остальных вершин как бесконечные for (int i = 0; i < V; i++) dist[i] = INT_MAX; dist[src] = 0; // Шаг 2: ослабить все ребра |V| - 1 раз. // Простой кратчайший путь из src в любую // другую вершину может иметь самое большее |V| - 1 ребро for (int i = 1; i <= V - 1; i++) { for (int j = 0; j < E; j++) { int u = graph->edge[j].src; int v = graph->edge[j].dest; int weight = graph->edge[j].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) dist[v] = dist[u] + weight; } } // Шаг 3: проверка циклов с отрицательным весом. // Вышеуказанный шаг гарантирует кратчайшие расстояния, // если график не содержит отрицательный весовой цикл. // Если мы получим более короткий путь, тогда будет цикл. for (int i = 0; i < E; i++) { int u = graph->edge[i].src; int v = graph->edge[i].dest; int weight = graph->edge[i].weight; if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) return true; } return false; } // Программа драйвера для проверки вышеуказанных функций int main() { // Создадим график, приведенный в примере выше int V = 4; // Количество вершин в графе int E = 7; // Количество ребер в графе Graph *graph = createGraph(V, E); graph = generateGraph(graph, V, E); Graph *temp = graph; for (int i = 0; i < E; i++) cout << temp->edge[i].src << "-" << temp->edge[i].dest << " " << temp->edge[i].weight << endl; cout << "Отрицательный весовой цикл: "; if (isNegCycleBellmanFord(graph, 0)) cout << "есть"; else cout << "нет"; return 0; }