关于prim
  • 板块学术版
  • 楼主南瓜桐
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/7/27 22:14
  • 上次更新2023/10/27 18:05:52
查看原帖
关于prim
439327
南瓜桐楼主2022/7/27 22:14

证明:Prim算法之所以是正确的,主要基于一个判断:对于任意一个顶点v,连接到该顶点的所有边中的一条最短边(v, vj)必然属于最小生成树(即任意一个属于最小生成树的连通子图,从外部连接到该连通子图的所有边中的一条最短边必然属于最小生成树) ---来源

其中,如何证明? 对于任意一个顶点v,连接到该顶点的所有边中的一条最短边(v, vj)必然属于最小生成树 如何证明?

2022/7/27 22:14
加载中...