Prim算法-最小生成树

基本思想:

1 置S={1}

2 只要S是V的真子集就做如下的贪心选择:

  选取满足条件的i ,i属于S,j输入V-S,且c[i][j]最小的边,并将定点j加入S中

  这个过程直到S==V为止。

3 这个过程所选的边,恰好就是最小生成树

算法描述:

void Prim(int n,Type * * c)
{
    T = 空集;
    S = {1};
    while(S != V)
    {
        (i,j)=i 属于 S 且 j属于V-S的最小权边;
        T = T∪{(i,j)};
        S = S ∪ {j};
    }
}

模版代码:

template <class Type>
vodi Prim(int n,Type * * c)
{
    Type lowcost[maxint];
    int closest[maxint];
    bool s[maxint];
    s[1] = true;
    for(int i=2;i<=n;i++)
    {
        lowcost[i] = c[1][i];
        closest[i] = 1;
        s[i] = false;
    }
    for(int i = 1;i<n;i++)
    {
        Type min = inf;
        int j = 1;
        for(int k = 2;k <= n;k++)
            if((lowcost[k]<min) && (!s[k]))
            {
                min = lowcost[k];
                j=k;
            }
        cout<<j<<' '<<closest[j]<<endl;
        s[j] = true;
        for(k = 2;k<= n;k++)
            if((c[j][k]<lowcost[k])&&(!s[k]))
            {
                lowcost[k] = c[j][k];
                closest[k] = j;
            }
    }
}

本文转自博客园xingoo的博客,原文链接:Prim算法-最小生成树,如需转载请自行联系原博主。

时间: 2024-11-10 09:55:04

Prim算法-最小生成树的相关文章

最小生成树之Prim算法

Prim算法: 假设N = (V,{E})是连通网,TE是N上最小生成树中边的集合.算法从U={u0}(u0属于V),TE={}开始,重复执行下述操作:在所有u属于U,v属于V-U的边(u,v)属于E中找到一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止,此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树. 为实现这个算法,需附设一个辅助数组closedge,以记录从U到V-U具有最小代价的边.对每个顶点vi属于V-U,在辅助数组中存在一个相应分量clos

c++-数据结构-Prim算法,最小生成树

问题描述 数据结构-Prim算法,最小生成树 写的最小堆模板套一个边结点老是报错,求解决方法 解决方案 多贴点代码吧. 是不是少了MSTEdgeNode所在的头文件 解决方案二: 错误那句,后面那个连着的>>中间改成这样> >,中间隔一个空格 解决方案三: 最小生成树 给定一无向带权图,顶点数是n,要使图连通只需n-1条边,若这n-1条边的权值和最小,则称有这n个顶点和n-1条边构成了图的最小生成树(minimum-cost spanning tree). Prim算法 Prim算

谢谢-PRIM算法求最小生成树

问题描述 PRIM算法求最小生成树 对给定的网和起点,用PRIM算法的基本思想求解出所有的最小生成树, 解决方案 http://www.cnblogs.com/Veegin/archive/2011/04/29/2032388.html 解决方案二: 简单来说思路就是从小到大遍历所有的边,依次添加到图中,如果这个边添加进去会造成回路,就不添加它,找下一个,直到所有的顶点都加入 解决方案三: http://blog.csdn.net/yeruby/article/details/38615045

最小生成树算法之Prim算法_C 语言

本文介绍了最小生成树的定义,Prim算法的实现步骤,通过简单举例实现了C语言编程. 1.什么是最小生成树算法? 简言之,就是给定一个具有n个顶点的加权的无相连通图,用n-1条边连接这n个顶点,并且使得连接之后的所有边的权值之和最小.这就叫最小生成树算法,最典型的两种算法就是Kruskal算法和本文要讲的Prim算法. 2.Prim算法的步骤是什么? 这就要涉及一些图论的知识了. a.假定图的顶点集合为V,边集合为E. b.初始化点集合U={u}.//u为V中的任意选定的一点 c.从u的邻接结点中

图的生成树(森林)(克鲁斯卡尔Kruskal算法和普里姆Prim算法)、以及并查集的使用

图的连通性问题:无向图的连通分量和生成树,所有顶点均由边连接在一起,但不存在回路的图. 设图 G=(V, E) 是个连通图,当从图任一顶点出发遍历图G 时,将边集 E(G) 分成两个集合 T(G) 和 B(G).其中 T(G)是遍历图时所经过的边的集合,B(G) 是遍历图时未经过的边的集合.显然,G1(V, T) 是图 G 的极小连通子图,即子图G1 是连通图 G 的生成树. 深度优先生成森林   右边的是深度优先生成森林: 连通图的生成树不一定是唯一的,不同的遍历图的方法得到不同的生成树;从不

Prim算法(三) Java详解

普里姆算法介绍 普里姆(Prim)算法,是用来求加权连通图的最小生成树的算法. 基本思想 对于图G而言,V是所有顶点的集合:现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边.从所有uU,v(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树中的所有边. 普里姆算法图解 以上图G4为例,来对普里姆进

Prim算法(二) C++详解

普里姆算法介绍 普里姆(Prim)算法,是用来求加权连通图的最小生成树的算法. 基本思想 对于图G而言,V是所有顶点的集合:现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边.从所有uU,v(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树中的所有边. 普里姆算法图解 以上图G4为例,来对普里姆进

Prim算法(一) C语言详解

普里姆算法介绍 普里姆(Prim)算法,和克鲁斯卡尔算法一样,是用来求加权连通图的最小生成树的算法. 基本思想 对于图G而言,V是所有顶点的集合:现在,设置两个新的集合U和T,其中U用于存放G的最小生成树中的顶点,T存放G的最小生成树中的边.从所有uU,v(V-U) (V-U表示出去U的所有顶点)的边中选取权值最小的边(u, v),将顶点v加入集合U中,将边(u, v)加入集合T中,如此不断重复,直到U=V为止,最小生成树构造完毕,这时集合T中包含了最小生成树中的所有边. 普里姆算法图解 以上图

经典算法题每日演练——第十四题 Prim算法

        图论在数据结构中是非常有趣而复杂的,作为web码农的我,在实际开发中一直没有找到它的使用场景,不像树那样的频繁使用,不过还是准备 仔细的把图论全部过一遍. 一:最小生成树        图中有一个好玩的东西叫做生成树,就是用边来把所有的顶点联通起来,前提条件是最后形成的联通图中不能存在回路,所以就形成这样一个 推理:假设图中的顶点有n个,则生成树的边有n-1条,多一条会存在回路,少一路则不能把所有顶点联通起来,如果非要在图中加上权重,则生成树 中权重最小的叫做最小生成树. 对于上