您当前的位置: 首页 >  数据结构与算法

星拱北辰

暂无认证

  • 0浏览

    0关注

    1205博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【数据结构与算法】深度探究Prim算法和Kruskal算法

星拱北辰 发布时间:2022-02-09 23:37:52 ,浏览量:0

Prim算法的算法框架

所谓算法框架,其实就是大概的一个步骤,说白了就是每一步该做什么。

Prim是一种贪心的最小生成树算法,适合于边稠密的图。

  • 初始时从图中仁取义顶点加入树T,此时树中只含有一个顶点。
  • 选择一个与当前T中顶点集合距离最近的顶点,并将该顶点和相应的边加入T,每次操作后T的顶点数和边数都加1。
  • 以此类推,直到图中所有的顶点都并入T,得到的T就是最小生成树,此时T中必有n-1条边。

Prim算法伪代码:

void prim(G, T) {
   
    // 初始化空树
    T = ∅;
    // 添加任意顶点w
    U = {
   w}
关注
打赏
1660750074
查看更多评论
立即登录/注册

微信扫码登录

0.0423s