克鲁斯卡尔算法代码easyx

克鲁斯卡尔算法（Kruskal's Algorithm）是一种用于寻找最小生成树（Minimum Spanning Tree, MST）的贪心算法。最小生成树是指在一个加权无向连通图中，包含所有顶点且边权之和最小的生成树。克鲁斯卡尔算法的基本思想是每次选择一条权重最小的边，并且这条边不会形成环，直到所有顶点都被连接。

以下是使用C++和EasyX库实现的克鲁斯卡尔算法的代码示例：

#include <graphics.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Subset {
    int parent, rank;
};

int V, E;
vector<Edge> edges;
vector<Edge> result;

int find(Subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void Union(Subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

int compare(const void* a, const void* b) {
    Edge* a1 = (Edge*)a;
    Edge* b1 = (Edge*)b;
    return a1->weight - b1->weight;
}

void KruskalMST() {
    qsort(&edges[0], edges.size(), sizeof(edges[0]), compare);

    Subset* subsets = new Subset[V];
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    int e = 0;
    int i = 0;

    while (e < V - 1 && i < edges.size()) {
        Edge next_edge = edges[i++];

        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        if (x != y) {
            result.push_back(next_edge);
            Union(subsets, x, y);
            e++;
        }
    }

    delete[] subsets;
}

int main() {
    initgraph(800, 600);

    cout << "Enter number of vertices: ";
    cin >> V;
    cout << "Enter number of edges: ";
    cin >> E;

    cout << "Enter each edge (src dest weight):" << endl;
    for (int i = 0; i < E; ++i) {
        Edge edge;
        cin >> edge.src >> edge.dest >> edge.weight;
        edges.push_back(edge);
    }

    KruskalMST();

    for (int i = 0; i < result.size(); ++i) {
        int x1 = result[i].src * 50;
        int y1 = result[i].src * 50;
        int x2 = result[i].dest * 50;
        int y2 = result[i].dest * 50;

        line(x1, y1, x2, y2);
    }

    getchar();
    closegraph();
    return 0;
}

这个示例代码展示了如何使用C++和EasyX库实现克鲁斯卡尔算法。代码首先读取顶点和边的信息，然后使用克鲁斯卡尔算法找到最小生成树，并在图形界面中绘制出来。