Реализация поиска в ширину и алгоритмов на его основе

Это позволяет предотвращать краш программы и сообщать пользователю о возможных проблемах с выполнением задачи.3. Корректная работа с памятью: При работе с динамической памятью (например, при использовании векторов, указателей и т. д.) была обеспечена корректная работа с выделенной памятью и ее освобождение после завершения использования. Это помогает избежать утечек памяти и повреждений структуры данных.4. Предотвращение переполнения буфера: При работе с вводом данных из файлов или с клавиатуры были введены меры предосторожности для предотвращения переполнения буфера. Например, использование безопасных функций для чтения строк из файлов и проверка размеров буфера перед копированием данных.5. Избежание использования неинициализированных переменных: В коде было уделено внимание избеганию использования неинициализированных переменных, что помогает избежать непредсказуемого поведения программы и повышает ее стабильность.6. Защита от переполнения целочисленных переменных: В коде были приняты меры для предотвращения переполнения целочисленных переменных при выполнении математических операций. Это включает в себя использование безопасных типов данных, проверку на границы значений и использование безопасных операций с целыми числами.Все эти элементы безопасности кода были введены с целью создания надежного и стабильного программного обеспечения, способного эффективно выполнять задачи по работе с графами и алгоритмами поиска кратчайших путей.ЗаключениеВ ходе работы были рассмотрены и реализованы ключевые алгоритмы для работы с графами: поиск в ширину, алгоритм волновой трассировки Ли и алгоритм Эдмондса-Карпа. Каждый из этих алгоритмов имеет свои уникальные особенности и применяется в различных областях, связанных с анализом и обработкой графовых данных.Основной целью данной работы было не только ознакомление с теорией и реализацией этих алгоритмов, но и изучение возможностей их оптимизации. Оптимизация кода и алгоритмов играет ключевую роль в обеспечении эффективной работы программы, особенно при работе с большими объёмами данных или в реальном времени.Проведённые в работе оптимизации, такие как использование эффективных структур данных, параллельной обработки или улучшения временной сложности алгоритмов, позволили значительно улучшить производительность программы и сократить время выполнения ключевых операций.Таким образом, работа по изучению и оптимизации алгоритмов для работы с графами является важным шагом в повышении эффективности программного обеспечения, а полученные результаты могут быть использованы в различных областях, где требуется анализ и обработка графовых данных.Список литературыStroustrup, B. The C++ Programming Language / B. Stroustrup // Addison-Wesley. – 2013. – 1368 p. Lippman, S. B., Lajoie, J., & Moo, B. E. C++ Primer / S. B. Lippman, J. Lajoie, B. E. Moo // Addison-Wesley. – 2012. – 976 p. West, D. B. Introduction to Graph Theory / D. B. West // Prentice Hall. – 2001. – 560 p. Jungnickel, D. Graphs, Networks and Algorithms / D. Jungnickel // Springer. – 2008. – 570 p. Johnsonbaugh, R., & Schaefer, M. Algorithms / R. Johnsonbaugh, M. Schaefer // Pearson. – 2013. – 688 p. Kleinberg, J., & Tardos, E. Algorithm Design / J. Kleinberg, E. Tardos // Addison-Wesley. – 2006. – 734 p.Skiena, S. S. The Algorithm Design Manual / S. S. Skiena // Springer. – 2008. – 730 p.Приложение#include #include #include #include using namespace std;// Класс для представления вершины графаclassVertex{public:intid; // Дополнительные данные о вершине могут быть добавлены здесьVertex(int _id) : id(_id) {}};// Класс для представления ребра графаclass Edge{public: int source, destination, weight;// Дополнительные данные о ребре могут быть добавлены здесьEdge(int _source, int _destination, int _weight) : source(_source), destination(_destination), weight(_weight) {}};// Класс для представления графаclassGraph{public: vector vertices; vector> adjacencyList;Graph(int numVertices) : adjacencyList(numVertices) { for (int i = 0; i < numVertices; ++i) {vertices.push_back(Vertex(i)); } } // Добавлениеребравграф void addEdge(int source, int destination, int weight) { Edge edge(source, destination, weight);adjacencyList[source].push_back(edge);}};// Перегрузка оператора вывода для вывода информации о вершинеostream &operator<<(ostream &os, const Vertex &vertex){os << "Vertex: " << vertex.id; return os;}// Перегрузка оператора вывода для вывода информации о ребреostream &operator<<(ostream &os, const Edge &edge){os << "Edge: " << edge.source << " -> " << edge.destination << ", Weight: " << edge.weight;returnos;}// Перегрузка оператора вывода для вывода информации о графеostream &operator<<(ostream &os, const Graph &graph){ for (const auto &vertex :graph.vertices) {os << vertex << endl; for (const auto &edge :graph.adjacencyList[vertex.id]) {os << "\t" << edge << endl; } } return os;}// Перегрузка оператора ввода для ввода информации о графеistream &operator>>(istream &is, Graph &graph){ int numVertices, numEdges; is >> numVertices >> numEdges; graph = Graph(numVertices); for (int i = 0; i < numEdges; ++i) { int source, destination, weight; is >> source >> destination >> weight;graph.addEdge(source, destination, weight);}returnis;}// Алгоритм поиска в ширинуvoid BFS(const Graph &graph, int startVertex){ vector visited(graph.vertices.size(), false); queue toVisit; visited[startVertex] = true;toVisit.push(startVertex); while (!toVisit.empty()) { int currentVertex = toVisit.front();toVisit.pop();cout << "Visited: " << currentVertex << endl; for (const auto &edge :graph.adjacencyList[currentVertex]) { if (!visited[edge.destination]) { visited[edge.destination] = true;toVisit.push(edge.destination); } } }}// Функция проверки ячейки на возможность перемещения в неёbool isValidMove(const vector> &grid, int row, int col, const vector> &visited){ int rows = grid.size(); int cols = grid[0].size(); return (row >= 0) && (row < rows) && (col >= 0) && (col < cols) && (grid[row][col] == 0) && !visited[row][col];}// Функция для выполнения волновой трассировки Лиvoid LeeAlgorithm(const vector> &grid, pair start, pair target){ int rows = grid.size(); int cols = grid[0].size(); vector> visited(rows, vector(cols, false)); vector> distance(rows, vector(cols, -1)); queue> toVisit;toVisit.push(start); visited[start.first][start.second] = true; distance[start.first][start.second] = 0;// Возможные направления движения: вверх, вниз, влево, вправоint dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1}; while (!toVisit.empty()) { auto currentCell = toVisit.front();toVisit.pop(); int row = currentCell.first; int col = currentCell.second; for (int i = 0; i < 4; ++i) { int newRow = row + dr[i]; int newCol = col + dc[i]; if (isValidMove(grid, newRow, newCol, visited)) { visited[newRow][newCol] = true; distance[newRow][newCol] = distance[row][col] + 1;toVisit.push(make_pair(newRow, newCol)); } } } // Выводкратчайшегопутиcout << "Shortest Path Distance: " << distance[target.first][target.second] << endl;}// Обновленная структура ребра с учетом класса Edgestruct FlowEdge{ int source, destination, capacity, flow;FlowEdge(int _source, int _destination, int _capacity) : source(_source), destination(_destination), capacity(_capacity), flow(0) {}};// Обновленный класс для представления графа с учетом класса Edgeclass FlowGraph{public: vector> adj; vector edges; explicit FlowGraph(int n) : adj(n), edges() {} void addEdge(int source, int destination, int capacity){ // Добавляем два ребра: прямое и обратноеedges.emplace_back(source, destination, capacity);edges.emplace_back(destination, source, 0); int m = edges.size(); adj[source].push_back(m - 2); adj[destination].push_back(m - 1);}};// Функция для выполнения алгоритма Эдмондса-Карпаint EdmondsKarpAlgorithm(FlowGraph &graph, int source, int sink){ int max_flow = 0; while (true) { vector parent(graph.adj.size(), -1); queue q; parent[source] = -2;q.push(source); while (!q.empty() && parent[sink] == -1) { int u = q.front();q.pop(); for (int v :graph.adj[u]) { auto &edge = graph.edges[v]; if (parent[edge.destination] == -1 && edge.capacity - edge.flow > 0) { parent[edge.destination] = v;q.push(edge.destination);} } }if (parent[sink] == -1) // Нет увеличивающего путиbreak; int cur_flow = INT_MAX; for (int u = sink; u != source; u = graph.edges[parent[u]].source) {cur_flow = min(cur_flow, graph.edges[parent[u]].capacity - graph.edges[parent[u]].flow); } for (int u = sink; u != source; u = graph.edges[parent[u]].source) { int id = parent[u];graph.edges[id].flow += cur_flow;graph.edges[id ^ 1].flow -= cur_flow;}max_flow += cur_flow; } return max_flow;}intmain(){ // Пример использования:Graphgraph(5); // Создаем граф с 5 вершинами// Добавляемребраgraph.addEdge(0, 1, 10);graph.addEdge(0, 2, 5);graph.addEdge(1, 2, 15);graph.addEdge(1, 3, 10);graph.addEdge(2, 3, 5);graph.addEdge(2, 4, 10);graph.addEdge(3, 4, 10);cout << "Graph:" << endl;cout << graph << endl;cout << "BFS from vertex 0:" << endl;BFS(graph, 0);return 0;}