数据结构之图论（续）
2020-04-27 16:48
程序猿声
关注
＃define inf （1 ＜＜ 30）using namespace std；const int maxn ＝ 110；const int maxm ＝ 5e5 ＋ 50；int dis［110］；map
NO．4最小生成树之Krusal
Prim算法是把我们要的树先假设为空，这是一种思路，接下来我们就来介绍下另外一种经典算法Krusal算法。
我们首先假设 WN＝（V，｛E｝） 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n－1条边为止。
这种方法与prim算法有着一定的相似之处，但是Krusal算法可以同时存在多个树，但在prim算法中同时只能有两个树。
与此同时我们也可以用STL进行优化操作．
＃include
分享
声明：
本文由入驻维科号的作者撰写，观点仅代表作者本人，不代表OFweek立场。如有侵权或其他问题，请联系举报。
图片新闻
技术文库
最新活动更多
-
即日-12.26立即报名>>> 【在线会议】村田用于AR/VR设计开发解决方案
-
1月8日火热报名中>> Allegro助力汽车电气化和底盘解决方案优化在线研讨会
-
1月9日立即预约>>> 【直播】ADI电能计量方案：新一代直流表、EV充电器和S级电能表
-
即日-1.14火热报名中>> OFweek2025中国智造CIO在线峰会
-
即日-1.16立即报名>>> 【在线会议】ImSym 开启全流程成像仿真时代
-
即日-1.20限时下载>>> 爱德克（IDEC）设备及工业现场安全解决方案
推荐专题
发表评论
请输入评论内容...
请输入评论/评论长度6~500个字
暂无评论
暂无评论