V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
HuaAn9527
V2EX  ›  程序员

如何检测社交网络中两个人是否是朋友关系(union-find 算法)

  •  2
     
  •   HuaAn9527 · 2021-02-22 10:09:47 +08:00 · 2307 次点击
    这是一个创建于 1370 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore

    程序员常用的 IDEA 插件:https://github.com/silently9527/ToolsetIdeaPlugin

    完全开源的淘客项目:https://github.com/silently9527/mall-coupons-server

    前言

    春节放假会了老家,停更了很多天,这是年后连夜肝出来的第一篇文章,先来聊聊春节放假期间发生的事,这次回家遇到了我学生时代的女神,当年她在我心目中那是

    "出淤泥而不染、濯清涟而不妖"

    没想到这次遇到了她,身体发福,心目中女神的形象瞬间碎了,就像达芬奇再次遇到了蒙娜丽莎

    "菡萏香销翠叶残"

    好了,言归正传。

    有时候我们可以需要判断在大型网络中两台计算机是否相连,是否需要建立一条新的连接才能通信;或者是在社交网络中判断两个人是否是朋友关系(相连表示是朋友关系)。在这种应用中,通常我们可能需要处理数百万的对象和数亿的连接,如何能够快速的判断出是否相连呢?这就需要使用到 union-find 算法

    概念

    相连

    假如输入一对整数,其中每个数字表示的是某种对象(人、地址或者计算机等等),整数对 p,q 理解为“p 与 q 相连”,相连具有以下特性:

    • 自反性:p 与 p 是相连的
    • 对称性:如果 p 与 q 相连,那么 q 与 p 相连
    • 传递性:如果 p 与 q 相连,q 与 r 相连,那么 p 与 r 也相连

    对象如何与数字关联起来,后面我们聊到一种算法符号表

    等价类

    假设相连是一个种等价关系,那么等价关系能够将对象划分为多个等价类,在该算法中,当且仅当两个对象相连时他们才属于同一个等价类

    触点

    整个网络中的某种对象称为触点

    连通分量

    将整数对称为连接,将等价类称作连通分量或者简称分量

    动态连通性

    union-find 算法的目标是当程序从输入中读取了整数对 p q 时,如果已知的所有整数对都不能说明 p q 是相连的,那么将这一对整数输出,否则忽略掉这对整数;我们需要设计数据结构来保存已知的所有整数对的信息,判断出输入的整数对是否是相连的,这种问题叫做动态连通性问题。

    union-find 算法 API 定义

    public interface UF {
        void union(int p, int q); //在 p 与 q 之间添加一条连接
    
        int find(int p); //返回 p 所在分量的标识符
    
        boolean connected(int p, int q); //判断出 p 与 q 是否存在于同一个分量中
    
        int count(); //统计出连通分量的数量
    }
    

    如果两个触点在不同的分量中,union 操作会使两个分量归并。一开始我们有 N 个分量(每个触点表示一个分量),将两个分量归并之后数量减一。

    抽象实现如下:

    public abstract class AbstractUF implements UF {
        protected int[] id;
        protected int count;
    
        public AbstractUF(int N) {
            count = N;
    
            id = new int[N];
            for (int i = 0; i < N; i++) {
                id[i] = i;
            }
        }
    
        @Override
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
    
        @Override
        public int count() {
            return count;
        }
    }
    

    接下来我们就主要来讨论如何实现 union 方法和 find 方法

    quick-find 算法

    这种算法的实现思路是在同一个连通分量中所有触点在 id[]中的值都是相同的,判断是否连通的 connected 的方法就是判断 id[p]是否等于 id[q]。

    public class QuickFindImpl extends AbstractUF {
        public QuickFindImpl(int N) {
            super(N);
        }
    
        @Override
        public int find(int p) {
            return id[p];
        }
    
        @Override
        public void union(int p, int q) {
            int pId = find(p);
            int qId = find(q);
    
            if (pId == qId) { //如果相等表示 p 与 q 已经属于同一分量中
                return;
            }
    
            for (int i = 0; i < id.length; i++) {
                if (id[i] == pId) {
                    id[i] = qId; //把分量中所有的值都统一成 qId
                }
            }
            count--; //连通分量数减一
        }
    
    }
    
    • 算法分析: find()操作显然是很快的,时间复杂度 O(1), 但是 union 的算法是无法处理大型数据的,因为每次都需要变量整个数组,那么 union 方法的时间复杂度是 O(n)

    quick-union 算法

    为了提高 union 方法的速度,我们需要考虑另外一种算法;使用同样的数据结构,只是重新定义 id[]表示的意义,每个触点所对应的 id[]值都是在同一分量中的另一个触点的名称

    在数组初始化之后,每个节点的链接都指向自己; id[]数组用父链接的形式表示了森林,每一次 union 操作都会找出每个分量的根节点进行归并。

    public class QuickUnionImpl extends AbstractUF {
        public QuickUnionImpl(int N) {
            super(N);
        }
    
        @Override
        public int find(int p) {
            //找出 p 所在分量的根触点
            while (p != id[p]) {
                p = id[p];
            }
            return p;
        }
    
        @Override
        public void union(int p, int q) {
            int pRoot = find(p); //找出 q p 的根触点
            int qRoot = find(q);
            if (pRoot == qRoot) { //处于同一分量不做处理
                return;
            }
            id[pRoot] = qRoot; //根节点
            count--;
        }
    
    }
    
    • 算法分析: 看起来 quick-union 算法比 quick-find 算法更快,因为 union 不需要为每对输入遍历整个数组, 考虑最佳情况下,find 方法只需要访问一次数组就可以得到根触点,那么 union 方法的时间复杂度 O(n); 考虑到最糟糕的输入情况,如下图:

    find 方法需要访问数组 n-1 次,那么 union 方法的时间复杂度是 O(n²)

    加权 quick-union 算法

    为了保证 quick-union 算法最糟糕的情况不在出现,我需要记录每一个树的大小,在进行分量归并操作时总是把小的树连接到大的树上,这种算法构造出来树的高度会远远小于未加权版本所构造的树高度。

    public class WeightedQuickUnionImpl extends AbstractUF {
        private int[] sz;
    
        public WeightedQuickUnionImpl(int N) {
            super(N);
            sz = new int[N];
            for (int i = 0; i < N; i++) {
                sz[i] = 1;
            }
        }
    
        @Override
        public void union(int p, int q) {
            int pRoot = find(p); //找出 q p 的根触点
            int qRoot = find(q);
            if (pRoot == qRoot) { //处于同一分量不做处理
                return;
            }
            //小树合并到大树
            if (sz[pRoot] < sz[qRoot]) {
                sz[qRoot] += sz[pRoot]; 
                id[pRoot] = qRoot;
            } else {
                sz[pRoot] += sz[qRoot];
                id[qRoot] = pRoot;
            }
            count--;
        }
    
        @Override
        public int find(int p) {
            //找出 p 所在分量的根触点
            while (p != id[p]) {
                p = id[p];
            }
            return p;
        }
    }
    
    • 算法分析: 最坏的情况下,每次 union 归并的树都是大小相等的,他们都包含了 2 的 n 次方个节点,高度都是 n,合并之后的高度变成了 n+1,由此可以得出 union 方法的时间复杂度是 O(lgN)

    总结

    union-find 算法只能判断出给定的两个整数是否是相连的,无法给出具体达到的路径;后期我们聊到图算法可以给出具体的路径

    算法 union() find()
    quick-find 算法 N 1
    quick-union 算法 树的高度 树的高度
    加权 quick-union 算法 lgN lgN

    文中所有源码已放入到了 github 仓库https://github.com/silently9527/JavaCore

    参考书籍:算法第四版

    10 条回复    2021-02-23 09:09:35 +08:00
    Olament
        1
    Olament  
       2021-02-22 11:03:01 +08:00
    Path compression 呢
    theRealWhexy
        2
    theRealWhexy  
       2021-02-22 11:13:30 +08:00 via iPhone
    第一次看到并查集写得这么长。厉害了!👍️
    Baratheon
        3
    Baratheon  
       2021-02-22 11:13:47 +08:00   ❤️ 1
    根据邓巴指数的指导……150 个人作为社交关系上限的情况下,对这玩意儿的检测可能有点多余
    ThanksSirAlex
        4
    ThanksSirAlex  
       2021-02-22 11:19:55 +08:00
    实际业务都用图数据库了,只不过图数据库里面本身可能会用并查集做查找
    lance6716
        5
    lance6716  
       2021-02-22 11:50:55 +08:00 via Android
    所以就是把<算法第四版>的代码搬运了一下?
    jones2000
        6
    jones2000  
       2021-02-22 12:09:02 +08:00
    "如何检测社交网络中两个人是否是朋友关系?"
    首先你要把这两个人的个人信息和隐私(同学,亲戚,同事,各个聊天软件里的好友等等.......)都收集到, 然后才是算法。
    yianing
        7
    yianing  
       2021-02-22 12:12:00 +08:00 via Android   ❤️ 1
    我的朋友的朋友,不一定是我的朋友
    no1xsyzy
        8
    no1xsyzy  
       2021-02-22 15:44:04 +08:00
    并查集的英文是 Disjoint-set
    时间复杂度是反 Ackermann 函数……
    顺便,每次搜索可以把整条路上的节点全部设到根节点上去。
    用递归写这一段非常爽 find_parent(s): s.parent = find_parent(s.parent)
    hanxiV2EX
        9
    hanxiV2EX  
       2021-02-22 15:49:22 +08:00
    @yianing 可能是敌人
    Ethson
        10
    Ethson  
       2021-02-23 09:09:35 +08:00
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1388 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 17:34 · PVG 01:34 · LAX 09:34 · JFK 12:34
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.