6. обходы графа II

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <locale>
#include <windows.h>

using namespace std;

class Graph {
private:
    map<string, map<string, int>> AdjList;
    bool direct;
    bool weight;

public:
    Graph(map<string, map<string, int>> a, bool d, bool w) {
        AdjList = a;
        direct = d;
        weight = w;
    }

    Graph(const Graph& g) {
        this->AdjList = g.AdjList;
        this->direct = g.direct;
        this->weight = g.weight;
    }

    void operator()(const Graph& g) {
        this->AdjList = g.AdjList;
        this->direct = g.direct;
        this->weight = g.weight;
    }

    Graph() {
        AdjList.clear();
        direct = false;
        weight = 0;
    }

    ~Graph() {
        direct = false;
        weight = false;
        AdjList.clear();
    }

    bool GetDir() {
        return this->direct;
    }

    bool GetWeight() {
        return this->weight;
    }

    void SetDir(bool d) {
        this->direct = d;
    }

    void SetWeight(bool w) {
        this->weight = w;
    }

    bool ExistVertex(string v) {
        return AdjList.find(v) != AdjList.end();
    }

    bool ExistEdge(string v1, string v2) {
        return AdjList.find(v1)->second.find(v2) != AdjList.find(v1)->second.end();
    }

    map <string, map<string, int>> GetAdj() {
        return this->AdjList;
    }

    void AddVertex(string v) {
        if (!ExistVertex(v)) {
            map<string, int> second;
            AdjList.insert({ v, second });
        }
        else {
            cout << "Вершина уже существует" << endl;
        }
    }

    void AddEdge(string v1, string v2) {   //для невзвешенного
        if (!ExistVertex(v1) || !ExistVertex(v2)) {
            cout << "Вершин не существует\n";
        }
        else {
            if (ExistEdge(v1, v2)) {
                cout << "Ребро уже существует!\n";
            }
            else {
                AdjList[v1][v2];
                if (!direct) {
                    AdjList[v2][v1];
                }
            }
        }
    }

    void AddEdge(string v1, string v2, int w) { //для взвешенного
        if (!ExistVertex(v1) || !ExistVertex(v2)) {
            cout << "Вершин не существует\n";
        }
        else {
            if (ExistEdge(v1, v2)) {
                cout << "Ребро уже существует!\n";
            }
            else {
                AdjList[v1][v2] = w;
                if (!direct) {
                    AdjList[v2][v1] = w;
                }
            }
        }
    }

    void DeleteVertex(string v) {
        if (ExistVertex(v) == false) {
            cout << "Вершины не существует\n";
        }
        else {
            for (auto& it : AdjList) {
                if (it.second.find(v) != it.second.end()) {
                    it.second.erase(v);
                }
            }
            AdjList.erase(v);
        }
    }

    void DeleteEdge(string v1, string v2) {
        if (ExistEdge(v1, v2)) {
            map<string, map<string, int>>::iterator i;
            map<string, int>::iterator j;

            i = AdjList.find(v1);
            j = i->second.find(v2);
            i->second.erase(j);
            if (!direct) {
                AdjList.find(v2)->second.erase(v1);
            }
        }
        else {
            cout << "Ребра не существует\n";
        }
    }

    void PrintList() {
        if (weight) {
            for (auto& elem : AdjList) {
                cout << "vertex " << elem.first + ": ";
                for (auto& it : elem.second) {
                    cout << it.first << " (w = " << it.second << "); ";
                }
                cout << "\n";
            }
            cout << "\n";
        }
        else {
            for (auto& elem : AdjList) {
                cout << "vertex " << elem.first + ": ";
                for (auto& it : elem.second) {
                    cout << it.first << "; ";
                }
                cout << "\n";
            }
            cout << "\n";
        }
    }

    void loadFromFile(string filename) {
        ifstream in(filename);
        if (!in.is_open()) {
            throw runtime_error("Не удалось открыть файл для чтения.");
        }
        string dir;
        in >> dir;
        if (dir == "directed") {
            direct = true;
        }
        else if (dir == "undirected") {
            direct = false;
        }
        else {
            throw runtime_error("Неверный формат файла: не указано directed или undirected\n");
        }

        string type;
        in >> type;
        if (type == "weighted") {
            weight = true;
        }
        else if (type == "unweighted") {
            weight = false;
        }
        else {
            throw runtime_error("Неверный формат файла: не указано weighted или unweighted\n");
        }

        if (weight) {
            string u, v;
            int weight;
            while (in >> u >> v >> weight) {
                if (!ExistVertex(u)) {
                    AddVertex(u);
                }
                if (!ExistVertex(v)) {
                    AddVertex(v);
                }
                AddEdge(u, v, weight);
            }
        }
        else {
            string u, v;
            while (in >> u >> v) {
                if (!ExistVertex(u)) {
                    AddVertex(u);
                }
                if (!ExistVertex(v)) {
                    AddVertex(v);
                }
                AddEdge(u, v);
            }
        }
    }

    void Task6(string u) {
        if (!ExistVertex(u)) {
            cout << "вершина не существует" << endl;
            return;
        }

        for (auto& i : AdjList) {
            string v = i.first;
            map<string, bool> visited;
            map<string, string> way;
            queue<string> q;

            visited[v] = true;
            q.push(v);

            while (!q.empty()) {
                string current = q.front();
                q.pop();

                for (auto& ngb : AdjList[current]) {
                    if (!visited[ngb.first]) {
                        visited[ngb.first] = true;
                        way[ngb.first] = current;
                        q.push(ngb.first);
                    }
                }
            }

            if (visited[u]) {
                vector<string> path;
                for (string at = u; !at.empty(); at = way[at]) {
                    path.push_back(at);
                }
                reverse(path.begin(), path.end());

                cout << "Кратчайший путь от " << v << " до " << u << ": ";
                for (size_t i = 0; i < path.size(); ++i) {
                    cout << path[i];
                    if (i < path.size() - 1) {
                        cout << "; ";
                    }
                }
                cout << "\n";
            }
            else {
                cout << "нет пути \n";
            }
        }
    }
};


#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <locale>
#include <windows.h>
#include "Graph.h"

using namespace std;

int main() {
    setlocale(LC_ALL, "Russian");
    SetConsoleOutputCP(CP_UTF8);
    map<string, Graph> graphs;

    //меняем граф
    string c = "prim1.txt";
    Graph g1;
    g1.loadFromFile(c);
    graphs[c] = g1;

    //задание 6
    string another_v;
    cout << "Введите номер вершины: ";
    cin >> another_v;
    g1.Task6(another_v);
}