【算法笔记】普里姆Prim算法的简单实现

水深无声 2021-09-26 16:28 391阅读 0赞

### 前言 ###

由于最近在学习数据结构，在学习的过程中动手把算法的思路用代码的形式实现了，这样记忆更深刻。所以在此记录下学习普里姆算法时，如何通过该算法获得连通网的最小生成树。

### 算法实现思路 ###

一、创建以邻接矩阵为存储方式的带权连通无向图（连通网）  
二、利用Prim算法计算最小边的权值之和  
（1）从图中任取一个顶点，把它当成一棵树，并用vest\[\]记录顶点是否在生成树中  
（2）从图中选取与该树相接的边中权值最小的边，并将与该边连接的顶点并入树中  
（3）重复步骤2直到图中所有顶点都被并入树中为止

### 算法实现代码 ###

#include <stdio.h>
    #include <stdlib.h>
    
    //图的邻接矩阵存储结构
    typedef char VertexType;
    typedef int EdgeType;
    
    #define MAXVEX 100 //最大顶点数
    #define INFINITY 65535 //用65535代表无穷远，表示不相邻
    
    typedef struct
    {
        VertexType vexs[MAXVEX];//顶点表
        EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵，可看作边表
        int vexNum,arcNum;//图中当前的顶点数和边数
    }MGraph;
    
    //建立无向网图的邻接矩阵表示
    void CreateMGraph(MGraph *G)
    {
        int i,j,k,w;
        printf("输入顶点数和边数(顶点数，边数)：\n");
        scanf("%d,%d",&G->vexNum,&G->arcNum);//输入顶点数和边数
        getchar();
    
        printf("输入顶点字符(字符串形式)：\n");
        for(i=0;i<G->vexNum;i++)//读入顶点信息，建立顶点表
            scanf("%c",&G->vexs[i]);
    
        for(i=0;i<G->vexNum;i++)
            for(j=0;j<G->vexNum;j++)
                G->arc[i][j]=INFINITY;//邻接矩阵初始化
    
        for(k=0;k<G->arcNum;k++)//读入arcNum条边，建立邻接矩阵
        {
            printf("输入边（vi,vj）上的顶点i，顶点j和权w：\n");
            scanf("%d,%d,%d",&i,&j,&w);//输入边（vi,vj）上的权w
    
            G->arc[i][j]=w;
            G->arc[j][i] = G->arc[i][j];//因为是无向图，矩阵对称
        }
    }
    
    /** * v0为任意一顶点 */
    void Prim(MGraph g,int v0){
        int vset[MAXVEX],lowcast[MAXVEX];
        int i,j,k,sum,min;
        for(i=0;i<g.vexNum;++i){ 
        // lowcast[i]保存与当前树相接的边的权值
          lowcast[i]=g.arc[v0][i];
          vset[i]=0;
        }
       // vset[i]=1表示顶点并入生成树中
        vset[v0]=1;
       // 累计树的权值
        sum=0;    
       // 从与树相接的边中选取一条权值最小的边，并将与该边连接的顶点并入树中
        for(i=0;i<g.vexNum-1;++i){
           min=INFINITY;  // INFINITY是已定义的比图中所有边权值都大的常量
           for(j=0;j<g.vexNum;++j){
             // 如果顶点已在树中，则不对其进行操作
             // 找到权值最小的边及其所连接的顶点
             if(vset[j]==0&&lowcast[j]<min){
                min=lowcast[j];
                k=j;
             }
           }
           vset[k]=1;
           sum+=min;
           for(j=0;j<g.vexNum;++j){
              // 对当前生成树中的顶点的相接的边进行比较，更新与剩余顶点的边的最小权值
              if(vset[j]==0&&g.arc[k][j]<lowcast[j]){
                 lowcast[j]=g.arc[k][j];
              }
           }
        }
        printf("最小权值之和：%d\n",sum);
    }
    
    
    int main()
    {
        MGraph G;
        CreateMGraph(&G);
        Prim(G,0);
        return 0;
    }

> 参考资料：  
> [图的存储结构——邻接矩阵的创建][Link 1]

[Link 1]: https://blog.csdn.net/zhangguannan0101/article/details/37319477