最新消息:点击查看大S的省钱秘笈

最小生成树Prim算法朴素版 C语言实现

编程相关 Slyar 1591浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

前几天研究Kruskal算法,直接上手就是并查集优化,朴素算法压根就没写。这两天看Prim算法也想略过朴素版O(n^2)直接用二叉堆优化,可是发现不看朴素算法根本写不出来...囧,看来还是不能忽略基础...

草稿纸上画图模拟推演了半天,终于搞清楚Prim算法朴素版的C语言实现,拿出那天学Kruskal的小题目测试了一下,通过。

代码的注释我写得很详细,方便理解,有几点需要说明一下。

1、2个for循环都是从2开始的,因为一般我们默认开始就把第一个节点加入生成树,因此之后不需要再次寻找它。

2、lowcost[i]记录的是以节点i为终点的最小边权值。初始化时因为默认把第一个节点加入生成树,因此lowcost[i] = graph[1][i],即最小边权值就是各节点到1号节点的边权值。

3、mst[i]记录的是lowcost[i]对应的起点,这样有起点,有终点,即可唯一确定一条边了。初始化时mst[i] = 1,即每条边都是从1号节点出发。

编写程序:对于如下一个带权无向图,给出节点个数以及所有边权值,用Prim算法求最小生成树。

kruskal

输入数据:

7 11
A B 7
A D 5
B C 8
B D 9
B E 7
C E 5
D E 15
D F 6
E F 8
E G 9
F G 11

输出:

A - D : 5
D - F : 6
A - B : 7
B - E : 7
E - C : 5
E - G : 9
Total:39

最小生成树Prim算法朴素版 C语言实现 代码如下

转载请注明:Slyar Home » 最小生成树Prim算法朴素版 C语言实现

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (20)

  1. 结果不对啊
    随便说说2年前 (2015-03-29)回复
  2. 谢啦谢啦.
    鸢尾2年前 (2014-08-01)回复
  3. 我QQ827193289
    耀2年前 (2014-07-31)回复
  4. 谢谢,帮了我大忙,废话不多说,有事的找帮忙的话,能帮的一定帮
    耀2年前 (2014-07-31)回复
  5. 学习了
    汪汪汪奋进3年前 (2013-10-02)回复
  6. 输入时第一行的那个数字7和11是什么意思
    36503年前 (2013-08-16)回复
    • 7个点,11条边
      鸢尾2年前 (2014-08-01)回复
  7. 好东西
    张静4年前 (2013-04-18)回复
  8. 不错
    张静4年前 (2013-04-18)回复
  9. 就是对的
    Slyar4年前 (2012-08-23)回复
  10. 第五行 lowcost[minid] = 0; 貌似应该改为mst[minid]=0吧 注释很详细 不过希望LZ把正确的东西拿出来分享~
    ly4年前 (2012-08-14)回复
  11. c语言代码都对应解释,智力不错,人品也好。
    xiehua8104年前 (2012-07-13)回复
  12. 写的非常详细,小弟这里谢过了!
    匿名5年前 (2012-02-01)回复
  13. 不错,拿走了。
    BinGo6年前 (2011-06-25)回复
  14. 感谢lz,但有几个小错误,if (lowcost[j] < min && lowcost[j] != 0)还要判断加入树没 if (graph[minid][j] < lowcost[j])也要判断加入树没,还有是否有通
    匿名6年前 (2011-03-09)回复
  15. 非常感谢
    匿名6年前 (2010-10-15)回复
  16. 非常感谢,很好用
    匿名6年前 (2010-07-18)回复
  17. @ 错就错吧
    Slyar8年前 (2009-07-03)回复
  18. 结果出不来 错误。。
    匿名8年前 (2009-07-03)回复
  19. 学习了。
    笨猫8年前 (2009-06-06)回复