侵权投诉
订阅
纠错
加入自媒体

数据结构之图论(续)

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

<上一页  1  2  3  
声明: 本文由入驻维科号的作者撰写,观点仅代表作者本人,不代表OFweek立场。如有侵权或其他问题,请联系举报。

发表评论

0条评论,0人参与

请输入评论内容...

请输入评论/评论长度6~500个字

您提交的评论过于频繁,请输入验证码继续

暂无评论

暂无评论

电子工程 猎头职位 更多
扫码关注公众号
OFweek电子工程网
获取更多精彩内容
文章纠错
x
*文字标题:
*纠错内容:
联系邮箱:
*验 证 码:

粤公网安备 44030502002758号