数据结构——邻接矩阵的最小生成树Prim算法

矫情吗；* 2022-08-12 16:07 152阅读 0赞

#include <iostream>
    #include <iomanip>
    using namespace std;
            
    #define MAX_VERTEX_NUM    10        //最大顶点个数
    #define INFINITY 32768   
    typedef char VerType;
    typedef int VRType;
    typedef struct
    {
        VerType    vexs[MAX_VERTEX_NUM];    //顶点向量
        int        arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];                    //邻接矩阵
        int        vexnum,arcnum;            //图的当前顶点数和弧数
    }mgraph, * MGraph;
    typedef struct 
    {
        VerType adjvex;        
        VRType    lowcost;
    }closedge[MAX_VERTEX_NUM];//记录从顶点集U到V-U的代价最小的边的辅助数组定义
    
    
    //初始化图
    void init_mgraph(MGraph &g)    
    {
        g=(MGraph)malloc(sizeof(mgraph));
        g->vexnum=0;
        g->arcnum=0;
        for(int i=0;i<MAX_VERTEX_NUM;i++)
            g->vexs[i]=0;
        for(i=0;i<MAX_VERTEX_NUM;i++)
            for(int j=0;j<MAX_VERTEX_NUM;j++)
                g->arcs[i][j]=INFINITY;
    }
    
    void add_vexs(MGraph &g)    //增加顶点
    {
        cout<<"请输入顶点的个数:"<<endl;
        cin>>g->vexnum;
        cout<<"请输入顶点的值"<<endl;
        for(int i=0;i<g->vexnum;i++)
        {
            cin>>g->vexs[i];
        }
    }
    void add_arcs(MGraph &g)    //增加边
    {
        cout<<"请输入边的个数:"<<endl;
        cin>>g->arcnum;
        VerType ch1,ch2;
        int weight;
        int row,col;
    
        for(int i=0;i<g->arcnum;i++)
        {    
            cin>>ch1>>ch2>>weight;
            for(int j=0;j<g->vexnum;j++)
            {
                if(g->vexs[j]==ch1)
                {
                    row=j;
                }
                if(g->vexs[j]==ch2)
                {
                    col=j;
                }
            }
            g->arcs[row][col]=weight;    //有向带权图只需把1改为weight
            g->arcs[col][row]=weight;
        }
    }
    void creat_mgraph(MGraph &g) //创建图    
    {
        add_vexs(g);    //增加顶点
        add_arcs(g);    //增加边
    }
    
    void print_mgraph(MGraph &g) //打印图
    {
        for(int i=0;i<g->vexnum;i++)
            cout<<"   "<<g->vexs[i]<<"  ";
        cout<<endl;
        for(i=0;i<g->vexnum;i++)
        {
            cout<<g->vexs[i];
            for(int j=0;j<g->vexnum;j++)
            {
                cout<<setw(5)<<g->arcs[i][j]<<" ";
            }
            cout<<endl;
        } 
    }
    
    //返回顶点v在顶点向量中的位置
    int LocateVex(MGraph &g, VerType v)
    {
            int i;
            for(i = 0; v != g->vexs[i] && i < g->vexnum; i++)
                    ;
            if(i >= g->vexnum)
                    return -1;
            return i;
    }
    //求出T的下一个节点，第k节点
    int minimun(MGraph &g, closedge closedge)
    {
        int min=INFINITY,k=0,i;
        for(i=0;i<g->vexnum;i++)
        {
            if(closedge[i].lowcost != 0 && closedge[i].lowcost < min)
            {
                min = closedge[i].lowcost;
                k = i;
            }
        }
        return k;
    }
    //普里姆算法
    void MiniSpanTree_Prim(MGraph &g, VerType u)    //普里姆算法从顶点u出发构造G的最小生成树T，输出T的各条边。
    {
        closedge closedge;
    
        int i,j;
        int k=LocateVex(g,u);    
        for(j=0;j<g->vexnum;j++)        //辅助数组初始化
        {
            if(j!=k)
            {
                closedge[j].adjvex=u;
                closedge[j].lowcost=g->arcs[k][j];
            }
        }
        closedge[k].lowcost = 0;    //初始，U={u}
    
        for(i=1;i<g->vexnum;i++)        //选择其余g.vexnum-1个顶点
        {
            k=minimun(g,closedge);        //求出T的下一个节点，第k节点
            cout<<closedge[k].adjvex<<"  "<<g->vexs[k]<<"  "<<closedge[k].lowcost<<endl;    //输出生成树的边
            closedge[k].lowcost=0;        //第k顶点并入U集
            
            for(j=0;j<g->vexnum;j++)
            {
                if(g->arcs[k][j] < closedge[j].lowcost)        //新顶点并入集后，选择新的边，将小的边放到辅助数组中
                {
                    closedge[j].adjvex = g->vexs[k];
                    closedge[j].lowcost = g->arcs[k][j];
                }
            }
        }
    }//MiniSpanTree_Prim
    
    int main()
    {
        MGraph G;
        init_mgraph(G);        //初始化图
        creat_mgraph(G);    //创建图
        print_mgraph(G);    //打印图
        MiniSpanTree_Prim(G,G->vexs[0]);    //最小生成树
    
        return 0;
    }