C语言数据结构普里姆算法-求最小生成树

我不是女神ヾ 2022-01-22 04:35 219阅读 0赞

/\*  
\*普里姆算法求最小生成树  
\*创建一个无向网  
\*创建一个保存每一行的最小权值和顶点值的结构体数组  
\*进行 每一次的数组更新  
\*最后直到生成一个无向网的最小生成树  
\*  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define MAX_SIZE  1024//顶点的最大数目
    #define NAME_SIZE 255
    #define OK 1
    #define ERROR 0
    #define MAX_INT 2025  //无限大的值
    typedef int ArcType;//图的权值的数据类型
    typedef char VertexType;//顶点数据的类型
    typedef int Statu;//返回值数据类型
    typedef struct edge
    {
        VertexType adjvex;//数组顶点的数据
        ArcType lowcost;//权值
    }closedge[MAX_SIZE];//最小权值的数组
    closedge edge;
    typedef struct
    {
        VertexType vexs[MAX_SIZE];//无向网的顶点数组
         ArcType arcs[MAX_SIZE][MAX_SIZE];//无向网的权值的二维数组
    
        int e;//图的边数
        int  n;//图的顶点数
    }AMGraph;//无向网的数据结构
    void create_minspantree_prim(AMGraph*G,VertexType v);//普里姆算法函数
    void test();//测试函数
    Statu creat_UDN(AMGraph*G);//创建无向网函数
    int Locate_vex(AMGraph*G,VertexType vex);//定位函数
    int min_index(AMGraph*G);//返回最小权值的下标
    
    void main()
    {
        test();//测试函数
    
    }
    Statu creat_UDN(AMGraph*G)//创建无向网函数
    {
        int i,j;
        VertexType vex1;
        VertexType vex2;
        int x,y;
        int now_weight;//当前的权值
        printf("请输入无向网的顶点数：");
        scanf("%d",&G->n);
        printf("请输入无向网的边数：");
        scanf("%d",&G->e);
     getchar();
        //初始化顶点的数据
        for(i=0;i<G->n;i++)
        {
            printf("顶点%d:：",i+1);
            scanf("%c",&G->vexs[i]);
         getchar();
        }
        //初始化权值的二维数组的信息
        for(i=0;i<G->n;i++)
            for(j=0;j<G->n;j++)
        {
            G->arcs[i][j]=MAX_INT;//对权值进行无限大赋值
    
        }
        //录入无向网中边的信息
        for(i=0;i<G->e;i++)
        {
            printf("顶点：");
            scanf("%c",&vex1);
         getchar();
            printf("邻接点：");
            scanf("%c",&vex2);
         getchar();
            printf("当前的权值：");
            scanf("%d",&now_weight);
         getchar();
            x=Locate_vex(G,vex1);
            y=Locate_vex(G,vex2);
            if(x==-1||y==-1)
            {
                return ERROR;
            }
            else
            {
                G->arcs[x][y]=now_weight;
                G->arcs[y][x]=G->arcs[x][y];//无向网权值的赋值
            }
    
    
        }
        return OK;
    }
    int Locate_vex(AMGraph*G,VertexType vex)
    {
        int index=0;
        while(index<G->n)
        {
            if(vex==G->vexs[index])
                break;
            else
                index++;
        }
        return (index==G->n? -1 :index);//三目运算符
    }
    void test()//测试函数
    {
        int i;
        int j;//临时变量
        AMGraph*G;
        G=(AMGraph*)malloc(sizeof(AMGraph));//申请动态存储空间
        int result=creat_UDN(G);
        if(result==ERROR)
        {
            printf("无向网创建失败,请重试!\n");
            return ;
        }
        else
        {
            //打印无向网
            printf("\t");
            //打印第一行的顶点数据
            for(i=0;i<G->n;i++)
            {
                printf("\t%c",G->vexs[i]);
            }
            printf("\n");//打印完第一行换行
            for(i=0;i<G->n;i++)
            {
                printf("\t%c",G->vexs[i]);//每一行打印一个顶点
                for(j=0;j<G->n;j++)
                {
                    if(G->arcs[i][j]==MAX_INT)
                    {
                        printf("\t∞");
                    }
                    else
                    {
                        printf("\t%d",G->arcs[i][j]);//输出其权值
    
                    }
                }
                printf("\n");
            }
        }
        printf("由普里姆算法得到的最下生成树为：\n");
        create_minspantree_prim(G,'A');
        printf("\n");
    }
    void create_minspantree_prim(AMGraph*G,VertexType v)//普里姆算法
    {
        int i,j,k;
        VertexType u0,v0;//输出两个顶点数据的临时变量
        k=Locate_vex(G,v);//得到根节点在顶点数组中的下标
        //初始化权值数组
        for(i=0;i<G->n;i++)
        {
            if(i!=k)//数组中没有权值最小的节点
            {
                edge[i].adjvex=v;
                edge[i].lowcost=G->arcs[k][i];
                //将第一个节点所在的第一行的权值输入到权值数组中
    
            }
        }
        edge[k].lowcost=0;
        //避免查找最小权值的边的另一个节点时再次遍历
        //继续循环输出权值最小的边
    
        for(i=0;i<G->n;i++)
        {
            k=min_index(G);//查找数组中的最小权值的节点的下标
            u0=G->vexs[k];//在数组中的最小权值的边的另一个节点值
            v0=edge[k].adjvex;//数组初始化时已经将顶点值全部赋值为顶点v
            if(k!=-1)
            printf("%c->%c   %d\n",v0,u0,edge[k].lowcost);
            //对最小生成树的边的的信息进行输出
            edge[k].lowcost=0;//将其赋值为0   作用同上
            for(j=0;j<G->n;j++)//对其权值数组进行更新
            {
                if(edge[j].lowcost>G->arcs[k][j])
                {
                    edge[j].lowcost=G->arcs[k][j];
                    edge[j].adjvex=G->vexs[k];
                }
            }
        }
    }
    int min_index(AMGraph *G)//顶点的定位函数
    {
        int min=MAX_INT;
        int i;
        int index=-1;//返回的下标
        for(i=0;i<G->n;i++)
        {
            if(min>edge[i].lowcost&&edge[i].lowcost!=0)
            {
                min=edge[i].lowcost;
                index=i;
            }
    
        }
      return index;
    }