克鲁斯卡尔最小生成树easyx

### 使用 EasyX 实现克鲁斯卡尔最小生成树算法

对于实现克鲁斯卡尔最小生成树算法，可以利用 EasyX 图形库来可视化这一过程。下面提供一段完整的 C++ 代码示例，该程序不仅实现了 Kruskal 算法逻辑，还通过图形界面展示了每一步的变化情况。

#### 定义数据结构与初始化工作
首先定义必要的数据结构用于存储节点、边以及并查集的信息：

#include <graphics.h>
#include <vector>
using namespace std;

struct Edge {
    int u, v;     // 边连接的两个顶点编号
    double w;      // 权重
};

// 并查集辅助函数
int find(int *parent, int i) { return (parent[i] == i) ? i : (parent[i] = find(parent, parent[i])); }
void unionSet(int *parent, int x, int y) { parent[find(parent, x)] = find(parent, y); }

const int MAX_POINTS = 10;
pair<int, int> points[MAX_POINTS]; // 存储各点坐标位置
vector<Edge> edges;                // 所有候选边列表
bool selected[MAX_POINTS][MAX_POINTS] = {}; // 记录已被选中的边

#### 绘制初始状态
绘制所有给定的点及其标签，并设置窗口大小适配这些点的位置分布：

void drawInit() {
    initgraph(800, 600);
    
    settextcolor(WHITE);
    for (int i = 0; i < MAX_POINTS; ++i) {
        circle(points[i].first, points[i].second, 20);
        outtextxy(points[i].first - 5, points[i].second + 25, to_string(i));
    }
}

#### 主要处理流程
按照权重升序排列所有的边之后依次尝试加入到当前森林中去构建MST:

void kruskalAlgorithm() {
    sort(edges.begin(), edges.end(), [](Edge a, Edge b){return a.w < b.w;});
    
    int n = sizeof(points)/sizeof(*points), mst_weight=0;
    int* parent = new int[n];
    for (int i = 0; i < n; ++i) parent[i] = i;

    for(auto& edge : edges){
        int pu = find(parent, edge.u), pv = find(parent, edge.v);

        if(pu != pv){
            line(points[edge.u].first, points[edge.u].second,
                 points[edge.v].first, points[edge.v].second);
            
            Sleep(500); // 延迟显示效果
            
            unionSet(parent, pu, pv);
            mst_weight += static_cast<int>(edge.w);
            selected[edge.u][edge.v]=selected[edge.v][edge.u]=true;
        }
    }
    
    delete[] parent;
}

int main(){
    srand(time(NULL));

    // 随机生成一些测试用的数据...
    for(int i=0;i<MAX_POINTS;++i){
        points[i]={rand()%700+50, rand()%500+50};
        
        for(int j=i+1;j<MAX_POINTS;++j){
            edges.push_back({i,j,hypot(points[j].first-points[i].first,
                                      points[j].second-points[i].second)});
        }
    }

    drawInit();
    kruskalAlgorithm();

    system("pause");
    closegraph();
    return 0;
}

这段代码能够很好地展示如何使用 EasyX 库配合 Kruskal 算法完成最小生成树问题求解的同时，在屏幕上动态呈现整个计算的过程[^1]。