Nexperia
2019-04-07 07:50
采纳率: 11.8%
浏览 1.8k

用普里姆算法或克鲁斯卡尔算法求下面无向带权图的最小生成树

用普里姆算法或克鲁斯卡尔算法求下面无向带权图的最小生成树
图片说明

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • 武松111 2019-08-10 14:40
    已采纳

    普里姆算法是选顶点
    假设从A点出发构造最小生成树,距离A点最近的是D点,连接AD;然后距离A、D最近的是B点,连接BD;然后距离A、D、B最近的是C点,连接BC;
    然后距离A、D、B、C最近的是F点,连接CF;然后距离A、D、B、C、F最近的是G,连接FG;然后距离A、D、B、C、F、G点最近的是E点,连接GE;
    然后距离A、D、B、C、F、G、E点最近的是H点,连接EH。
    最小生成树为ADBCFGEH
    克鲁斯卡尔算法是选边
    边权为2最小,连接BC,EG;然后边权为3最小,连接EH;然后边权为4最小,连接CF,AD;然后边权为5最小,连接BD,FG。
    最小生成树为ADBCFGEH

    点赞 打赏 评论
  • blownewbee 2019-04-07 09:59

    因为你是三零用户(0采纳,0声望,0悬赏)代码就不写了,说下思路

    首先把边按照权重排序,然后从小到大依次将边添加到图上,如果出现了回路,那么就跳过。直到所有的边都尝试过。

    点赞 打赏 评论

相关推荐 更多相似问题