ЯМП Лаба 3 2023 (Графы)

//Graph.h
#pragma once
#include <vector>
#include <fstream>
#include <iostream>
#include <limits>

using namespace std;

// Структура для представления ребра графа
struct Edge
{
    int destination; // Вершина, в которую ведет ребро
    int weight;      // Вес ребра
};

class Graph
{
private:
    int number_of_vertices;
    vector<vector<Edge>> graph;  //Представление графа в виде списка смежности

public:
    Graph();
    int get_number_of_vertices();
    void input(const string& filename);
    void floyd_warshall_algorithm(vector<vector<int>>& distances);
    void DFS(int vertex, vector<bool>& visited);
};


//Graph.cpp
#include "Graph.h"

extern int INF; // Значение "бесконечность"

Graph::Graph()
{
    number_of_vertices = 0;
}

int Graph::get_number_of_vertices()
{
    return number_of_vertices;
}

void Graph::input(const string& filename)
{
    ifstream file(filename);
    if (!file)
    {
        cout << "Не удалось открыть файл." << endl;
        return;
    }

    file >> number_of_vertices; // Считываем количество вершин графа

    graph.resize(number_of_vertices);

    // Считываем данные о ребрах графа из файла
    int u, v, weight;
    while (file >> u >> v >> weight)
    {
        graph[u].push_back({ v, weight });
    }

    file.close();
}

void Graph::floyd_warshall_algorithm(vector<vector<int>>& distances)
{
    // Элементы на диагонали матрицы расстояний равны 0
    for (int i = 0; i < number_of_vertices; i++)
        distances[i][i] = 0;

    // Заполнение матрицы расстояний из графа
    for (int u = 0; u < number_of_vertices; u++)
        for (Edge edge : graph[u])
            distances[u][edge.destination] = edge.weight;

    // Вычисление кратчайших путей между всеми парами вершин
    for (int k = 0; k < number_of_vertices; k++)
        for (int i = 0; i < number_of_vertices; i++)
            for (int j = 0; j < number_of_vertices; j++)
                // Если путь через вершину k короче текущего пути, обновляем его
                if (distances[i][k] != INF && distances[k][j] != INF && distances[i][k] + distances[k][j] < distances[i][j])
                    distances[i][j] = distances[i][k] + distances[k][j];
}

void Graph::DFS(int vertex, vector<bool>& visited)
{
    visited[vertex] = true; // Помечаем текущую вершину как посещенную
    cout << vertex << " "; // Выводим текущую вершину

    // Рекурсивно обходим все соседние вершины
    for (Edge edge : graph[vertex])
    {
        int next_vertex = edge.destination;
        if (!visited[next_vertex])
        {
            DFS(next_vertex, visited);
        }
    }
}


//Source.cpp
//Пример входного файла "graph.txt":
//Количество вершин
//u v weight
//u v weight
//
//где u - исходная вершина, v - конечная, weight - вес ребра

#include <iostream>
#include "Graph.h"

int INF = numeric_limits<int>::max(); // Значение "бесконечность"

int main()
{
    setlocale(LC_ALL, "rus");

    Graph graph;
    graph.input("graph.txt");

    int number_of_vertices = graph.get_number_of_vertices();

    // Инициализация матрицы расстояний
    vector<vector<int>> distances(number_of_vertices, vector<int>(number_of_vertices, INF));
    graph.floyd_warshall_algorithm(distances);

    // Вывод кратчайших путей
    cout << ' ' << '\t';
    for (int i = 0; i < number_of_vertices; i++)
        cout << i << '\t';
    cout << endl << endl;
    for (int i = 0; i < number_of_vertices; i++)
    {
        cout << i << '\t';
        for (int j = 0; j < number_of_vertices; j++)
        {
            if (distances[i][j] == INF)
            {
                cout << "нет пути" << '\t';
            }
            else
            {
                cout << distances[i][j] << '\t';
            }
        }
        cout << endl;
    }

    cout << "\nОбход в глубину: ";
    vector<bool> visited(number_of_vertices, false);
    graph.DFS(0, visited);
    cout << endl;

    return 0;
}