普里姆最小生成树算法

1. 适用范围:

1. 稠密图中生成最小生成树

2. 图关于最小生成树的性质:

1. 最小生成树所包含边判定定理
   1. 直观理解:
      1. 把图顶点分为两部分, 横跨这两部分的边有很多条
      2. 其中权值最小的横跨边, 为最小生成树内的某一条边
2. 最小生成树所需边
   1. 所需边=顶点总数-1

3. 算法思想:

1. 利用最小生成树所含边判定定理
   1. 在图中任选一个顶点, 把这个顶点作为一部分, 即最小生成树的一部分
   2. 把最小横跨边纳入最小生成树中
      1. 同时新的那个顶点也纳入到最小生成树中
   3. 此时横跨边更新, 需要重新找最小横跨边, 并将其纳入最小生成树中
   4. 持续以上步骤, 直到最小生成树包含所需边(顶点数-1)

4. 在C语言中实现:

4.1. 在邻接矩阵存储结构下

梗概:

1. 需要一个线性表(数组)来储存边, 第一个结点不使用
   1. 每个结点有三部分信息:
      1. 树内顶点指针域
         1. 存储树内某个顶点在该线性表中的位置(下标)
         2. 作为该边的一个顶点
      2. 较短边权值域
         1. 存储该边的权值
      3. 该结点在线性表中的位置
         1. 表示图中的某个顶点
            1. 作为该边的另一个顶点
         2. 用结点在线性表中的位置表示(下标)
   2. 该线性表有两个作用:
      1. 记录每个树外顶点的较短跨树边
         1. 每个树外顶点可能有多个跨树边, 只记录较短的, 作为一层筛选
      2. 记录最小生成树内的边
2. 每次都从所有较短跨树边中, 取最短的跨树边, 其为第二层筛选
3. 将这个最短跨树边纳入树中
   1. 令线性表中的对应边的权=0
      1. 作为树内的标记
4. 更新所有发生改变的较短树外边
   1. 只有新纳入顶点的相关边才是新的跨树边
      1. 只有新的跨树边比旧的跨树边小, 才需要记录
         1. 新的跨树边和旧的跨跨树边的树外顶点都一样
5. 继续取最短的跨树边, 直到树内边数量达到需求
6. 此时线性表中所有权为0的边都是树内边, 一起构成一棵树 代码:

struct{
    int adjvex;
    int lowcost;
}closedge[MAX_VERTEX_NUM+1];
MiniSpanTree_Prim(AdjMatrix *gn, int u){
//从顶点u开始寻找最小生成树
    /*先把顶点u归入树部分*/
    closedge[u].lowcost=0;
    /*把树外顶点的跨树边都初始化*/
    for(i=1;i<gn->vertex;i++){
        if(i!=u){
            closedge[i].adjvex=u;
            closedge[i].lowcost=gn->arcs[u][i].adj;
        }
    }
    /*不断扩大树内边,直到达到所需边*/
    for(e=1;e<-gn->vexnum-1;e++){
        /*在所有短权跨树边中选最短的*/
        v=Minium(closedge);
        /*把该边归入树中*/
        closedge[v].lowcost=0;
        /*更新所有短权跨树边*/
        for(i=1;i<=gn->vernum;i++){
            /*过滤掉树内边,再过滤掉较长的跨树边*/
            if(gn->arcs[v][i].adj<closedge[i].lowcost){
	            /*新的较短跨树边必定连接刚纳入的顶点*/
                closedge[i].lowcost = gn->arcs[v][i].adj;
                closedge[i].adjvex = v;
            }
        }
    }
    //closedge中权为0的边都是树的边
}

5. 该算法可视化

Prim MST Visualzation (usfca.edu)