void Kruskal(Graph* g) { int i, j, k = 0; struct { ElementType head; ElementType tail; EdgeType cost; }edge[MaxVexNum],t; int vexSet[MaxVexNum]; for (i = 0; i < g->vexNum; i++) { //遍历矩阵的下三角元素 for (j = 0; j < i; j++) { if (g->edge[i][j] != INFINITY) { edge[k].head = i; edge[k].tail = j; edge[k++].cost = g->edge[i][j]; } } } for (i = 0; i < g->vexNum; i++) vexSet[i] = i; //各个顶点自成一个连通分量 for (i = 0; i < g->edgeNum-1; i++) { for (j = g->edgeNum-1; j >= i + 1; j--) { if (edge[j].cost < edge[j - 1].cost) { t = edge[j-1]; edge[j-1] = edge[j]; edge[j] = t; } } } for (i = 0; i < g->edgeNum; i++) { int vs1, vs2; vs1 = vexSet[edge[i].head]; vs2 = vexSet[edge[i].tail]; if (vs1 != vs2) { printf("(%c,%c)", g->vex[edge[i].tail], g->vex[edge[i].head]); for (j = 0; j < g->edgeNum; j++) { if (vexSet[j] == vs2) vexSet[j] = vs1; } } } }

这是一个基于Kruskal算法实现的最小生成树算法。其思路是先将图中的所有边按照权值排序，然后从小到大依次加入边，如果加入的边不会形成环，则将其加入最小生成树中，否则舍弃该边。具体实现过程如下：

1. 定义一个结构体数组edge，记录每条边的起点、终点和权值；
2. 定义一个数组vexSet，记录每个顶点所属的连通分量，初始状态下每个顶点自成一个连通分量；
3. 将所有边按照权值从小到大排序；
4. 依次遍历每条边，如果该边的起点和终点不在同一个连通分量中，则将其加入最小生成树中，并将其起点所在的连通分量的所有顶点都归为终点所在的连通分量中。

其中，关键的部分就是如何判断一个边的起点和终点是否在同一个连通分量中。这里使用了一个数组vexSet来记录每个顶点所属的连通分量，初始状态下每个顶点自成一个连通分量。在遍历边的过程中，每当遇到一条边的起点和终点不在同一个连通分量中时，就将起点所在的连通分量中的所有顶点都归为终点所在的连通分量中，即将vexSet数组中所有值为起点所在连通分量的顶点都改为终点所在的连通分量的编号。这样，就可以很方便地判断起点和终点是否在同一个连通分量中了。

最后，遍历完所有边后，就得到了最小生成树。