Kruskal算法-最小生成树

算法思想:

1 将G的n个顶点看成n个孤立的连通分支,所有的边按权从小到大排序

2 当查看到第k条边时,

  如果断点v和w分别是当前的两个不同的连通分支t1和t2中的顶点时,就用边(v,m)j将t1,t2连接成一个连通分支,然后继续查看第k+1条边;

  如果端点v和w当前的同一个连通分支中,就直接查看第k+1条边

实现代码:

template <class Type>
class EdgeNode{
    friend ostream& operator<<(ostream&,EdgeNode<Type>);
    friend bool Kruskal(int,int,EdgeNode<Type> *,EdgeNode<Type> *);
    friend void main(void);
    public:
        operator Type() const{return weight;}
    private:
        Type weight;
        int u,v;
};
template <class Type>
bool Kruskal(int n,int e,EdgeNode<Type> E[],EdgeNode <Type> t[])
{
    MinHeap<EdgeNode<Type>> H(1);
    H.Initialize(E,e,e);
    UnionFind U(n);
    int k = 0;
    while(e && k<n-1)
    {
        EdgeNode<int> x;
        H.DeleteMin(x);
        e--;
        int a = U.Find(x.u);
        int b = U.Find(x.v);
        if(a != b)
        {
            t[k++] = x;
            U.Union(a,b);
        }
    }
    H.Deactivate();
    return (k == n-1);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

HDU 2438 Turn the corner(三分查找)

托一个学弟的福,学了一下他的最简便三分写法,然后找了一道三分的题验证了下,AC了一题,写法确实方便,还是我太弱了,漫漫AC路!各路大神,以后你们有啥好的简便写法...

30550
来自专栏Spark生态圈

[Spark SQL] 源码解析之Optimizer

optimizer 以及之后的模块都只会在触发了action操作后才会执行。优化器是用来将Resolved LogicalPlan转化为optimized Lo...

11720
来自专栏互联网研发闲思录

grpc使用客户端技巧

  grpc 使用技巧,最近在做的项目是服务端是go语言提供服务使用的是grpc框架。 java在实现客户端的时候,参数的生成大部分采用创建者模式。java在接...

51590
来自专栏逍遥剑客的游戏开发

WOW小地图生成

33130
来自专栏landv

c语言-扑克牌小魔术

18030
来自专栏xingoo, 一个梦想做发明家的程序员

Spark MLlib 之 aggregate和treeAggregate从原理到应用

由于treeAggregate是在aggregate基础上的优化版本,因此先来看看aggregate是什么.

16300
来自专栏deepcc

ip的正则表达式 完美版

47660
来自专栏大内老A

ASP.NET MVC的Model元数据与Model模板:将”ListControl”引入ASP.NET MVC

我们不仅可以创建相应的模板来根据Model元数据控制种类型的数据在UI界面上的呈现方法,还可以通过一些扩展来控制Model元数据本身。在某些情况下通过这两者的结...

38260
来自专栏码匠的流水账

聊聊eureka client的serviceUrl

eureka-client-1.8.8-sources.jar!/com/netflix/discovery/DiscoveryClient.java

29510
来自专栏木宛城主

PowerShell 获取Site Collection下被签出的文件

由于权限的设置,当文件被签出时导致别人不可见了,这对校验文件个数的人来说着实是件烦恼的事。幸好利用PowerShell,可以获取Site Collection下...

20870

扫码关注云+社区

领取腾讯云代金券