当前位置：首页 > article >正文

【数据机构】最小生成树（prim算法）

article 2024/9/20 21:40:19

一.引例

在n个城市之间建设通信网络，至少需要架设多少条通信线路？如果每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小？

二.生成树与生成森林

生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。

生成森林：在非连通图中，由每个连通分量都可以得到一颗生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。

三.最小生成树（Minimal Spanning Tree）

MST性质：

假设G=（V，E）是一个无向连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必存在一棵包含边（u，v）的最小生成树。

如何利用MST性质寻找最小生成树？

找到两个点集之间最小权值的边

如何处理点集，使得最小权值的边构成生成树？

1）从一个点出发，依次加入点形成点集（Prim）

2）从边出发，将点集合并，避免形成环（Kruskal）

四.Prim算法

1.基本思想：

设G=（V，E）是具有n个顶点的连通网，T=（U，TE）是G的最小生成树，T的初始状态为U={u0},TE={},重复执行下述操作：找一条代价最小的边（u，v）并入合集TE，同时v并入U，直至U=V。

2.代码实现：

template<class T>
void Prim(MGraph <T>G,int start){
    int i,j,n=G.getVertexNum(),k;
    struct node shortEdge[n];
    
    
    for(i=0;i<n;i++){
        shortEdge[i].lowcost=G.arc[start][i];
        shortEdge[i].adjvex=start;
    }
    shortEdge[start].lowcost=0;
    //起点放入集合U中
    
    for(i=0;i<n-1;i++){
        k=minEdge(shortEdge, n);//寻找最短边的邻接点k
        outputSMT(k, shortEdge[k]);//输出最小生成树路径
        shortEdge[k].lowcost=0;//将顶点k加入到集合U中
        for(j=0;j<n;j++){//调整数组shortEdge
            if(G.arc[k][j]<shortEdge[j].lowcost){
                shortEdge[j].lowcost=G.arc[k][j];
                shortEdge[j].adjvex=k;
            }
        }
    }
}

int minEdge(struct node shortEdge[],int n){
    int i,min=0,flag=1;
    for(i=0;i<n;i++){
        if(shortEdge[i].adjvex!=0&&flag){
            min=i;
            flag=0;
        }
        else if(shortEdge[i].adjvex!=0){
            if(shortEdge[i].lowcost<shortEdge[min].lowcost){
                min=i;
            }
        }
    }
    return min;
}

void outputSMT(int k,struct node shortEdge){
    cout<<"("<<shortEdge.adjvex<<","<<k<<")"<<shortEdge.lowcost;
}