7. Каркас (Краскала)

void Task7() {
        int n = this->CountVertices();
        int m = this->CountEdges();
        int i = 0;

        vector<pair<int, pair<string, string>>> edges;
        for (auto it = AdjList.begin(); it != AdjList.end(); it++) {
            for (auto jt = it->second.begin(); jt != it->second.end(); jt++) {
                if (it->first < jt->first) {
                    edges.push_back(make_pair(jt->second, make_pair(it->first, jt->first)));
                }
            }
        }

        sort(edges.begin(), edges.end());
        map<string, string> component;
        for (auto& vertex : AdjList) {
            component[vertex.first] = vertex.first;
        }

        vector<pair<string, string>> res;
        for (auto& edge : edges) {
            string u = edge.second.first;
            string v = edge.second.second;
            int weight = edge.first;
            if (component[u] != component[v]) {
                res.push_back(make_pair(u, v));
                string old_component = component[v];
                for (auto& pair : component) {
                    if (pair.second == old_component) {
                        pair.second = component[u];
                    }
                }
            }
        }

        sort(res.begin(), res.end());
        cout << "Остовное дерево" << endl;
        for (auto& edge : res) {
            cout << edge.first << " - " << edge.second << " (вес: " << AdjList[edge.first][edge.second] << ")" << endl;
        }
    }


//main.cpp

#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 с = "prim3.txt";
    Graph g;
    g.loadFromFile(с);
    graphs[с] = g;

    cout << "Задание 7\n";
    g.Task7();
    cout << "\n";
}