最小生成树问题---Prim算法学习

一个具有n个节点的连通图的生成树是原图的最小连通子集，它包含了n个节点和n-1条边。若砍去任一条边，则生成树变为非连通图；若增加一条边，则在图中形成一条回路。本文所写的是一个带权的无向连通图中寻求各边权和最小的生成树。

计算最小生成树的的方法是贪心，则必须满足一下两个条件：

1）不能形成回路；

2）在保证1满足的条件下添加尽可能小的边。

实现的算法有两种，kruskal算法，prim算法，本文只介绍prim算法；

过程：

1）输入：一个加权连通图，其中节点集合为V，边集合为E；

2）初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {}，为空；

3）重复下列操作，直到Vnew = V；

a:在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4）输出：使用集合Vnew和Enew来描述所得到的最小生成树。

int prim(){

    for(int i=1;i<=n;i++){

        dis[i]=Map[1][i];

    }

    vis[1]=1;

    for(int i=1;i<n;i++){

        int MIN=INF,x=-1;

        for(int j=1;j<=n;j++){

            if(!vis[j]&&dis[j]<MIN){//每一次都取该结点和其他相邻的结点的最小值

                MIN=dis[j];

                x=j;

            }

        }

        if(x==-1)return -1;

        ans+=MIN;

        vis[x]=1;//标记已经过的节点

        for(int j=1;j<=n;j++){

            if(!vis[j]&&dis[j]>Map[x][j]){//更新dis数组，

                dis[j]=Map[x][j];

            }

        }

    }return ans;

}

巴特西

最小生成树问题---Prim算法学习

最新文章

热门文章