乐趣区

关于java:如何检测社交网络中两个人是否是朋友关系unionfind算法

jiezi

前言

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

“ 出淤泥而不染、濯清涟而不妖 ”

没想到这次回家遇到了她，身材发福了，心目中女神的形象霎时碎了，就如同达芬奇再次遇到了蒙娜丽莎

“ 菡萏香销翠叶残 ”

好了，言归正传。

有时候咱们能够须要判断在大型网络中两台计算机是否相连，是否须要建设一条新的连贯能力通信；或者是在社交网络中判断两个人是否是敌人关系（相连示意是敌人关系）。在这种利用中，通常咱们可能须要解决数百万的对象和数亿的连贯，如何可能疾速的判断出是否相连呢？这就须要应用到 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

参考书籍：算法第四版

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

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

微信公众号：贝塔学 Java

退出移动版