鲁大师的最小生成树的Prim算法c++实现

向右看齐 2022-12-24 00:37 227阅读 0赞

> 不是很难理解，不过突然感觉 c++这个面向对象的语言被我用成了面向过程好可惜

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int MVNUM = 1e2 + 5;
    const int INF = 65535;
    
    //权值的数据类型
    typedef int VRType;
    //节点类型
    typedef char VertexType;
    
    
    typedef struct
    {
        
        //节点的映射表
        VertexType vextable[MVNUM];
        //弧的权值， 无边权值为 INF
        VRType adj[MVNUM][MVNUM];
        int vexnum, arcnum;
    }MGraph;
    
    typedef struct Prime_table
    {
        
        //边的出发点
        VertexType adjvex;
        //以当前顶点为端点的边最小权值
        VRType lowcost;
    }Prime_table;
    Prime_table closedge[MVNUM];
    
    //查找节点的对应的数组下标
    int LocateVex(MGraph G, VertexType u)
    {
        
        for (int i = 0; i < G.vexnum; i++)
        {
        
            if (G.vextable[i] == u)
                return i;
        }
    }
    
    int minimum (Prime_table *closedge, int vexnum)
    {
        
        int res = -1;
        int minlowcost = INF;
        for (int i = 0; i < vexnum; i++)
        {
        
            if (closedge[i].lowcost != 0)
            {
        
                if (closedge[i].lowcost < minlowcost)
                {
        
                    res = i;
                    minlowcost = closedge[i].lowcost;
                }
            }
        }
        return res;
    }
    
    void Print(VertexType u)
    {
        
        printf("%c ", u);
    }
    //用prime从顶点u出发 构造网的最小生成树
    //图用邻接矩阵来存储， u是图的一个节点
    //时间复杂度： n + (n-1)*(n + n) 约等于O(2n^2) 约等于 O(n^2)
    
    void MiniSpanTree_P(MGraph G, VertexType u)
    {
        
        int k = LocateVex(G, u);
        for (int j = 0; j < G.vexnum; j++)
        {
        
            if (j != k)
            {
        
                closedge[j].adjvex = u;
                closedge[j].lowcost = G.adj[k][j];
            }
        }
        closedge[k].lowcost = 0;
    
        for (int i = 1; i < G.vexnum; i++)
        {
        
            //找最小的边
            k = minimum(closedge, G.vexnum);
            Print(G.vextable[k]);
            closedge[k].lowcost = 0;
            for (int j = 0; j < G.vexnum; j++)
            {
        
                if (G.adj[k][j] < closedge[j].lowcost)
                {
        
                    closedge[j].adjvex = G.vextable[k];
                    closedge[j].lowcost = G.adj[j][k];
                }
            }
        }
    }
    
    int main()
    {
        
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        MGraph G;
        cin >> G.vexnum >> G.arcnum;
        for (int i = 0; i < G.vexnum; i++)
            cin >> G.vextable[i];
        for (int i = 0; i < G.vexnum; i++)
        {
        
            for (int j = 0; j < G.vexnum; j++)
            {
        
                G.adj[i][j] = INF;
                G.adj[j][i] = INF;
            }
        }
        for (int i = 0; i < G.arcnum; i++)
        {
        
            VRType weight;
            int pos1, pos2;
            VertexType v1, v2;
            cin >> v1 >> v2 >> weight;
    
            pos1 = LocateVex(G, v1);
            pos2 = LocateVex(G, v2);
            G.adj[pos1][pos2] = weight;
            G.adj[pos2][pos1] = weight;
        }
        MiniSpanTree_P(G, G.vextable[0]);
        return 0;
    }