聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

136页才写了两个算法……难怪劝退新人

2022-03-24 18:31 浏览: 2726361 次 我要评论(0 条) 字号:

以下文章来源于Coder梁 ,作者梁唐

Coder梁 .

一个热爱分享的推荐算法工程师

来自公众号:Coder梁

大家好,我是梁唐。

今天我们继续来解读《算法》这本书,我将会按照书中的顺序来依次来介绍算法。今天介绍的是本书的第二个算法——并查集。

并查集的英文叫union-find算法,顾名思义其实就是集合的合并和查找算法。不知道为啥,书里没用采用这个翻译,而是直接用的union-find这个英文名字。另外一个值得吐槽的是,这个全书第二出现的算法,它的位置在全书的第136页……这一百多页的内容都是在介绍一些Java中容器的使用,和数据抽象类的写法……

老梁个人认为这本书最大的问题就是选择了Java作为主语言,这就势必需要对Java的一些延伸花一定的篇幅介绍。比如类的封装,Java中容器的使用等等。大部分新手是不会选择Java作为学习算法的主力语言的,要么选择更传统的C++,要么就选择语法比较丰富的Python。当然也许作者有其它的考量,但从我个人的角度来说,对此不是非常理解。

好了,言归正传,我们回到算法上来。

对于并查集的应用场景,书中举了一个连通性的例子。在无向图当中,连通性具有传递性。

如果A点能够去往B点,那么说明A和B连通。所谓传递性是指,如果A和B连通,B和C连通,那么A和C也连通。

并查集解决的就是,假设我们有了一系列连通性,要求给定两点是否连通的问题。

在这个问题当中,麻烦的就是传递性的问题。两个点相连不仅意味着这两个点属于一个集合,而是意味着两个集合的合并。最简单的方式,我们可以用一个数组存储每个点所属的集合,我们给每一个集合一个编号。当两个集合合并时,我们遍历数组,将这两个集合中的所有元素的编号统一。当要判断两个元素是否属于同一个集合的时候,只需要判断一下这两个点的编号是否相同即可,这是的操作。

但显然这样做有一个比较大的问题,就是复杂度的问题。每一次合并集合我们都需要遍历所有的元素,当合并操作比较多的时候,显然这是不可接受的。

所以我们要做的就是针对这个问题进行优化。

怎么优化呢?

我们分析一下问题,在之前的方案当中之所以复杂度很高是因为我们每次需要遍历所有的元素,将所有元素的编号进行修改。因为我们判断元素是否同一个集合是依靠元素的编号实现的,在这种方式下就必须要对所有元素编号进行修改。

所以说想要优化这个问题,就必须要换一种方式。我们可以用一个很简单的数据结构很巧妙地解决这个问题,这个数据结构就是树。我们将属于同一个集合的节点放在同一棵树上,我们判断两个节点所在树的根节点是否相同,就可以知道它们是不是同属于一个集合了。

并且这样做还有一个好处,就是当我们需要合并两个集合时,只需要修改其中一个根节点,让它的父节点指向另外一棵树即可。

如上图所示,我们只需要将1的父节点指向8,就完成了两个集合的合并,再也不需要去遍历元素了。

我们把上面的逻辑写成代码,只有十行左右:

// 记录每个节点的父亲节点
vector<intfa(n, 0);

void init(int n) {
    for (int i = 0; i < n; i++) fa[i] = i;
}

int query(int x) {
    if (fa[x] == x)
       return x;
    return query(fa[x]);
}

void union(int a, int b) {
    int fa = query(a);
 int fb = query(b);
    if (fa == fb)
        return ;
    fa[fb] = fa;
}
            
bool is_same(int a, int b) {
 return query(a) == query(b);            
}

到这里就结束了吗?其实还没有,我们仔细思考会发现一个问题。就是我们用树结构来存储查找的时候会有一个树深的问题,我们要找到一个节点的根节点,需要沿着路径一路往上查找到树根,遍历的长度就是树深。那么显然树深是会影响模型的性能的。

对于我们来说,我们只关心树根,完全不关心树结构。那么我们很自然地可以想到,可以把树尽量拍平,这样的话树深就会尽量小,我们在查找的时候也就会更快。

但把树拍平也是需要开销的,我们手动去遍历节点拍平树就显得不是很有意义。这里我们可以采用一种特殊的做法——懒惰法。

所谓的懒惰法,也就是将一些开销比较大的操作滞后,只在必要的时候进行。

在这个问题当中,我们可以在每次查找的时候,将查找路径上的所有节点的父节点设为根节点。写出来代码也并不复杂:

int query(int x) {
 return x == fa[x] ? x : (fa[x] = query(fa[x]));
}

另外,我们还可以维护每棵树的最大深度,在合并的时候将树深较小的合并到树深较大的树上。

结合所有优化之后,代码如下:

// 记录每个节点的父亲节点
vector<intfa(n, 0);
vector<intrank(n, 0);

void init(int n) {
    for (int i = 0; i < n; i++) fa[i] = i;
}

int query(int x) {
    return x == fa[x] ? x : (fa[x] = query(fa[x]));
}

void union(int a, int b) {
    int f1 = query(a);
 int f2 = query(b);
    if (f1 == f2) return ;
    if (rank[f1] < rank[f1]) fa[f1] = f2;
    else {
        fa[f2] = f1;
        // 如果两棵树,树深相等,则合并之后树深需要+1
        if (rank[f1] == rank[f2]) rank[f2] ++;
    }
}

bool is_same(int a, int b) {
 return query(a) == query(b);            
}

这里的实现上和《算法》一书当中略有不同,书中判断的条件不是树深,而是元素的个数,这两种做法各有优劣,也没有谁对谁错。

通过元素判断合并的方式问题在于元素的多少并不一定和树深直接相关,而以树深为依据也有瑕疵,因为query的操作可能会影响树深。不过这两种做法并不会影响结果的正确性,都是可行的。

通过优化之后,我们的查找和合并操作都可以近似地接近于。关于复杂度,书中有详细的证明,这部分写得还是很好的,感兴趣的同学可以查阅一下。

关于并查集这个算法就聊到这里,感谢大家的阅读。

--- EOF ---


推荐↓↓↓


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复