“Алгоритм Краскала на C++”

Алгоритм Краскала – популярный алгоритм, используемый для поиска минимального остовного дерева в связном взвешенном графе. Вот реализация алгоритма Краскала на C++:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Structure to represent an edge in the graph
struct Edge {
    int src, dest, weight;
};
// Structure to represent a disjoint set
struct DisjointSet {
    vector<int> parent, rank;

    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n);

        // Initially, all vertices are in different sets and have rank 0
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
// Find the parent of a vertex
    int find(int v) {
        if (v != parent[v])
            parent[v] = find(parent[v]);
        return parent[v];
    }
// Union of two sets
    void Union(int x, int y) {
        int xroot = find(x);
        int yroot = find(y);

        if (rank[xroot] < rank[yroot])
            parent[xroot] = yroot;
        else if (rank[xroot] > rank[yroot])
            parent[yroot] = xroot;
        else {
            parent[yroot] = xroot;
            rank[xroot]++;
        }
    }
};
// Compare function for sorting edges based on their weight
bool compareEdges(Edge a, Edge b) {
    return a.weight < b.weight;
}
// Function to implement Kruskal's algorithm
vector<Edge> kruskals(vector<Edge>& edges, int V) {
    vector<Edge> result;

    // Sort the edges in non-decreasing order of their weight
    sort(edges.begin(), edges.end(), compareEdges);

    DisjointSet ds(V);

    for (Edge edge : edges) {
        int srcParent = ds.find(edge.src);
        int destParent = ds.find(edge.dest);

        // If including this edge does not form a cycle, include it in the result
        if (srcParent != destParent) {
            result.push_back(edge);
            ds.Union(srcParent, destParent);
        }
    }

    return result;
}
// Test the algorithm
int main() {
    int V, E;
    cout << "Enter the number of vertices: ";
    cin >> V;
    cout << "Enter the number of edges: ";
    cin >> E;

    vector<Edge> edges(E);

    cout << "Enter source, destination, and weight of each edge:\n";
    for (int i = 0; i < E; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    vector<Edge> minimumSpanningTree = kruskals(edges, V);

    cout << "Minimum Spanning Tree:\n";
    for (Edge edge : minimumSpanningTree) {
        cout << edge.src << " -- " << edge.dest << " \tWeight: " << edge.weight << endl;
    }

    return 0;
}