数据结构石玉强版的克鲁斯卡尔算法

克鲁斯卡尔算法是一种用于求解最小生成树的算法，其基本思想是从小到大逐步选取边，直到所有节点都被连接为止。下面是数据结构（C语言版）石玉强版的克鲁斯卡尔算法示例代码：

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

#define MAXVEX 100  //最大顶点数
#define MAXEDGE 100 //最大边数

//定义边结构体
typedef struct
{
    int u; //边的起点
    int v; //边的终点
    int w; //边的权值
}Edge;

//定义邻接矩阵结构体
typedef struct
{
    int vexs[MAXVEX]; //顶点数组
    int arc[MAXVEX][MAXVEX]; //邻接矩阵数组
    int numVertexes; //顶点数
    int numEdges; //边数
}MGraph;

//初始化图
void CreateMGraph(MGraph *G)
{
    int i,j,k,w;
    printf("输入顶点数和边数：\n");
    scanf("%d,%d",&G->numVertexes,&G->numEdges);

    for(i = 0; i < G->numVertexes; i++)
    {
        printf("输入第%d个顶点：",i+1);
        scanf("%d",&G->vexs[i]);
    }

    for(i = 0; i < G->numVertexes; i++)
    {
        for(j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j] = 0;
        }
    }

    for(k = 0; k < G->numEdges; k++)
    {
        printf("输入边（vi,vj）上的下标i，下标j和权值w：\n");
        scanf("%d,%d,%d",&i,&j,&w);
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];
    }
}

//初始化边集合
void InitEdge(MGraph G,Edge *edge)
{
    int i,j,k = 0;
    for(i = 0; i < G.numVertexes; i++)
    {
        for(j = i+1; j < G.numVertexes; j++)
        {
            if(G.arc[i][j] != 0)
            {
                edge[k].u = i;
                edge[k].v = j;
                edge[k].w = G.arc[i][j];
                k++;
            }
        }
    }
}

//排序
void SortEdge(Edge *edge,int n)
{
    int i,j;
    Edge tmp;
    for(i = 0; i < n-1; i++)
    {
        for(j = i+1; j < n; j++)
        {
            if(edge[i].w > edge[j].w)
            {
                tmp = edge[i];
                edge[i] = edge[j];
                edge[j] = tmp;
            }
        }
    }
}

//查找连通分量
int Find(int *parent,int f)
{
    while(parent[f] > 0)
    {
        f = parent[f];
    }
    return f;
}

//克鲁斯卡尔算法
void Kruskal(MGraph G)
{
    int i,j;
    Edge edge[MAXEDGE]; //边集合
    int parent[MAXVEX]; //定义一个数组用来判断边与边是否形成环路
    int n = 0; //记录边的个数
    InitEdge(G,edge);
    SortEdge(edge,G.numEdges);
    for(i = 0; i < G.numVertexes; i++)
    {
        parent[i] = 0;
    }
    for(i = 0; i < G.numEdges; i++)
    {
        int uf = Find(parent,edge[i].u);
        int vf = Find(parent,edge[i].v);
        if(uf != vf)
        {
            parent[uf] = vf;
            printf("(%d,%d)权值：%d\n",edge[i].u,edge[i].v,edge[i].w);
            n++;
        }
        if(n >= G.numVertexes-1) //边数等于顶点数减1时退出
        {
            break;
        }
    }
}

int main()
{
    MGraph G;
    CreateMGraph(&G);
    Kruskal(G);
    return 0;
}

需要注意的是，此代码仅供学习参考，实际使用中需要根据具体情况进行修改和完善。