问题描述 给定无向图带权图的数据类型如下 #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct { VertexType vexs[MAXVEX]; //顶点表 EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表 int vertexNum,edgeNum; }MGraph,*Graph; 请设计int Kruskal(Graph g)函数。 该函数用Kruskal算法求g的最小生成树的权,并返回最小生成树的权。 如果最小生成树不存在，则返回-1。 请注意，本题有预置代码，只需提交所要求的函数定义代码即可。

以下是题目所需的函数定义代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXVEX 100

typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vexs[MAXVEX]; //顶点表
    EdgeType edge[MAXVEX][MAXVEX]; //邻接矩阵,即边表
    int vertexNum, edgeNum;
}MGraph, *Graph;

//边的结构体
typedef struct {
    int begin, end; //边的起点和终点
    int weight; //边的权重
}Edge;

//并查集的结构体
typedef struct {
    int father[MAXVEX]; //父节点数组
    int rank[MAXVEX]; //秩数组
}UnionFindSet;

//交换两个边的信息
void swapEdge(Edge *e1, Edge *e2) {
    Edge tmp = *e1;
    *e1 = *e2;
    *e2 = tmp;
}

//对边进行快速排序
void quickSortEdge(Edge *edges, int left, int right) {
    if (left < right) {
        int i = left, j = right;
        Edge pivot = edges[left];
        while (i < j) {
            while (i < j && edges[j].weight >= pivot.weight) {
                j--;
            }
            edges[i] = edges[j];
            while (i < j && edges[i].weight <= pivot.weight) {
                i++;
            }
            edges[j] = edges[i];
        }
        edges[i] = pivot;
        quickSortEdge(edges, left, i - 1);
        quickSortEdge(edges, i + 1, right);
    }
}

//初始化并查集
void initUnionFindSet(UnionFindSet *ufs, int n) {
    for (int i = 0; i < n; i++) {
        ufs->father[i] = i;
        ufs->rank[i] = 0;
    }
}

//查找节点所在的集合
int find(UnionFindSet *ufs, int x) {
    if (ufs->father[x] != x) {
        ufs->father[x] = find(ufs, ufs->father[x]);
    }
    return ufs->father[x];
}

//合并两个集合
void unionSet(UnionFindSet *ufs, int x, int y) {
    int rootX = find(ufs, x);
    int rootY = find(ufs, y);
    if (rootX != rootY) {
        if (ufs->rank[rootX] > ufs->rank[rootY]) {
            ufs->father[rootY] = rootX;
        } else if (ufs->rank[rootX] < ufs->rank[rootY]) {
            ufs->father[rootX] = rootY;
        } else {
            ufs->father[rootY] = rootX;
            ufs->rank[rootX]++;
        }
    }
}

//Kruskal算法求最小生成树
int Kruskal(Graph g) {
    Edge edges[MAXVEX * MAXVEX];
    int edgeNum = 0;
    for (int i = 0; i < g->vertexNum; i++) {
        for (int j = i + 1; j < g->vertexNum; j++) {
            if (g->edge[i][j] != 0) {
                edges[edgeNum].begin = i;
                edges[edgeNum].end = j;
                edges[edgeNum].weight = g->edge[i][j];
                edgeNum++;
            }
        }
    }
    quickSortEdge(edges, 0, edgeNum - 1);
    UnionFindSet ufs;
    initUnionFindSet(&ufs, g->vertexNum);
    int minWeight = 0;
    int count = 0;
    for (int i = 0; i < edgeNum; i++) {
        Edge e = edges[i];
        if (find(&ufs, e.begin) != find(&ufs, e.end)) {
            unionSet(&ufs, e.begin, e.end);
            minWeight += e.weight;
            count++;
            if (count == g->vertexNum - 1) {
                break;
            }
        }
    }
    if (count != g->vertexNum - 1) {
        return -1;
    }
    return minWeight;
}

其中，`swapEdge()`函数用于交换两个边的信息，`quickSortEdge()`函数用于对边进行快速排序，`initUnionFindSet()`函数用于初始化并查集，`find()`函数用于查找节点所在的集合，`unionSet()`函数用于合并两个集合，`Kruskal()`函数用于实现Kruskal算法求最小生成树的权。