最小生成树之克鲁斯卡尔（Kruskal）算法编程提示如下：在矩阵中以上排序操作不方便编程，所以定义下面结构体存储边的信息。 typedef struct { int begin; // 边的起点 int end; // 边的终点 int weight; // 边的权重 bool selected; // 是否作为最小生成树的边，初值flase }Edge; // 定...-Go服务器开发

这是一个使用克鲁斯卡尔算法求最小生成树的示例代码。你可以根据提示将其编写成完整的程序。

#include <iostream>
#include <algorithm>
const int MAXVEX = 100;  // 最大顶点数
const int MAXEDGE = 100; // 最大边数
typedef struct
{
    int begin;      // 边的起点
    int end;        // 边的终点
    int weight;     // 边的权重
    bool selected;  // 是否作为最小生成树的边，初值false
} Edge;
int parent[MAXVEX];     // 用于寻找根节点的数组，初始化为 -1
Edge edges[MAXEDGE];    // 定义存储边的数组
// 找到顶点v所在树的根节点（递归实现）
int Find(int v)
{
    if (parent[v] == -1)
        return v;
    else
        return Find(parent[v]);
}
// 按照边的权重进行排序（从小到大）
bool Compare(const Edge& a, const Edge& b)
{
    return a.weight < b.weight;
}
void Kruskal(int vertexNum, int edgeNum)
{
    for (int i = 0; i < vertexNum - 1; i++)
    {
        for (int j = i + 1; j < vertexNum - 1; j++)
        {
            std::cin >> edges[edgeNum].begin >> edges[edgeNum].end >> edges[edgeNum].weight;
            edges[edgeNum].selected = false;
        }
    }
    std::sort(edges, edges + edgeNum, Compare); // 对边数组进行排序
    for (int i = 0; i < edgeNum; i++)
    {
        int n = Find(edges[i].begin);   // 找边的起点的根
        int m = Find(edges[i].end);     // 找边的终点的根
        // 两个顶点不在一棵子树内
        if (n != m)
        {
            parent[m] = n;
            edges[i].selected = true;
        }
    }
    // 输出所有选中的边
    for (int i = 0; i < edgeNum; i++)
    {
        if (edges[i].selected)
            std::cout << edges[i].begin << " - " << edges[i].end << " : " << edges[i].weight << std::endl;
    }
}
int main()
{
    int vertexNum, edgeNum;
    std::cin >> vertexNum >> edgeNum;
    Kruskal(vertexNum, edgeNum);
    return 0;
}