邻接矩阵+边集数组+克鲁斯卡尔

冷不防 2022-03-21 05:53 218阅读 0赞

### 题目描述： ###

利用克鲁斯卡尔的方法生成最小树。

##### 分析： #####

这个方法简单粗暴。  
邻接矩阵讲解：[https://blog.csdn.net/qq\_43506138/article/details/86599865][https_blog.csdn.net_qq_43506138_article_details_86599865]  
简单的讲，就是将边集数组中的边依次打印就好，不过在打印的前提是所要即将打印的这条边不会和之前打印的边成为回路。  
所以，这个方法只要在把边集数组转换出来后，在一个函数判断回路就可以了。

#include"stdio.h"
    #include"string.h"
    #include"stdlib.h"
    typedef char VertexType;
    typedef int EdgeType;
    #define MAXVEX 100
    #define MAXEDGE 100
    #define INFINITY 65535
    typedef struct
    {
        VertexType vexs[MAXVEX];
        EdgeType arc[MAXVEX][MAXVEX];
        int numEdge,numVexs;
    }MGraph;
    typedef struct
    {
        int begin;
        int end;
        int weight;
    }Edge;
    void CreateMGraph(MGraph *G)
    {
        int i,j,k,weight;
        printf("请输入顶点数和边数:\n");
        scanf("%d%d",&G->numVexs,&G->numEdge);
        for(i=0;i<G->numVexs;i++)   //初始化邻接矩阵
            for(j=0;j<G->numVexs;j++)
               {
                   if(i==j)
                      G->arc[i][j]=0;
                   else
                    G->arc[i][j]=INFINITY;
               }
        for(k=0;k<G->numEdge;k++)
        {
            printf("请输入边的相关信息（包括权）:\n");
            scanf("%d%d%d",&i,&j,&weight);
            G->arc[i][j]=weight;
            G->arc[j][i]=weight;
        }
    }
    //将邻接矩阵转化为边集数组
    void TransEdge(Edge edge[],MGraph *G)
    {
        int i,j,k=0;
        //依次将邻接矩阵中的有权的地方保存下来
        for(i=0;i<G->numEdge;i++)
            for(j=0;j<G->numEdge;j++)
                {
                    if(G->arc[i][j]!=0&&G->arc[i][j]!=INFINITY)
                    {
                        edge[k].begin=i;
                        edge[k].end=j;
                        edge[k].weight=G->arc[i][j];
                        k++;
                    }
                }
      //按照权排序
        for(i=0;i<k-1;i++)
            for(j=i+1;j<k;j++)
                {
                    if(edge[i].weight>edge[j].weight)
                    {
                        Edge T;
                        T=edge[i];edge[i]=edge[j];edge[j]=T;
                    }
                }
    }
    //查找连线顶点的尾部下标
    int Find(int *parent,int f)
    {
        while(parent[f]>0)
            f=parent[f];
        return f;
    }
    //最小生成树（克鲁斯卡尔）
    void MiniSpanTree_Kruskal(MGraph G)
    {
        int i,j,k;
        Edge edge[MAXEDGE];//边集数组
        int parent[MAXVEX];//判断边与边之间是否形成回路的用处
        for(i=0;i<MAXVEX;i++)//初始化parent
            parent[i]=0;
        TransEdge(edge,&G);//得到边集数组
        //循环每一条边
        for(i=0;i<G.numEdge;i++)
        {
            int n=Find(parent,edge[i].begin);
            int m=Find(parent,edge[i].end);
            if(n!=m)//成立则表示未成回路
            {//将此边的结尾顶点放入下标为起点的parent中
            //表示此顶点已经在生成树集合中
                parent[n]=m;
            //打印此边相关信息
                printf("(%d %d) :%d \n",edge[i].begin,edge[i].end,edge[i].weight);
            }
        }
    }
    int main()
    {
        MGraph G;
        CreateMGraph(&G);
        printf("邻接矩阵已创建完成，开始生成最小树（克鲁斯卡尔）：\n");
        MiniSpanTree_Kruskal(G);
    }

本代码难点在于Find函数和parent数组的理解，多演示几次就能很好理解了。简单的讲，Find函数，就是查找这个顶点线路的最后一个顶点

[https_blog.csdn.net_qq_43506138_article_details_86599865]: https://blog.csdn.net/qq_43506138/article/details/86599865