EasyX最小生成树代码

EasyX是一个简单易用的图形库，用于在Windows平台上进行图形界面的开发。最小生成树是一种常见的图论算法，用于在一个连通图中找到一棵生成树，使得树上所有边的权值之和最小。

以下是一个使用EasyX实现最小生成树算法的示例代码：

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

const int MAX_V = 100;  // 最大顶点数
const int INF = 0x3f3f3f3f;  // 无穷大

struct Edge {
    int u, v, weight;
};

int parent[MAX_V];  // 并查集数组

// 并查集的查找操作
int find(int x) {
    if (parent[x] == x)
        return x;
    return parent[x] = find(parent[x]);
}

// 并查集的合并操作
void merge(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY)
        parent[rootY] = rootX;
}

// 最小生成树算法
void kruskal(vector<Edge>& edges, int V) {
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.weight < b.weight;
    });

    for (int i = 0; i < V; i++)
        parent[i] = i;

    int edgeCount = 0;
    int treeWeight = 0;

    for (const auto& edge : edges) {
        int u = edge.u;
        int v = edge.v;
        int weight = edge.weight;

        if (find(u) != find(v)) {
            merge(u, v);
            treeWeight += weight;
            edgeCount++;

            // 在图形界面上绘制最小生成树的边
            line(u, v, GREEN);
            delay(500);  // 延时一段时间，以便观察绘制过程

            if (edgeCount == V - 1)
                break;
        }
    }

    cout << "最小生成树的权值之和为：" << treeWeight << endl;
}

int main() {
    initgraph(640, 480);  // 初始化图形界面

    vector<Edge> edges = {
        {0, 1, 4},
        {0, 7, 8},
        {1, 2, 8},
        {1, 7, 11},
        {2, 3, 7},
        {2, 8, 2},
        {2, 5, 4},
        {3, 4, 9},
        {3, 5, 14},
        {4, 5, 10},
        {5, 6, 2},
        {6, 7, 1},
        {6, 8, 6},
        {7, 8, 7}
    };

    kruskal(edges, 9);  // 执行最小生成树算法

    _getch();
    closegraph();  // 关闭图形界面

    return 0;
}

这段代码使用了EasyX库来绘制最小生成树的边，其中使用了并查集来判断是否形成环路。通过调用`kruskal`函数，可以执行最小生成树算法并在图形界面上绘制最小生成树的边。