朋友圈裂变算法具体实现之 Quick-Find
最近在整理一系列算法，也结合下自己涉及的业务进行思考。
问题产生于现实，实现过程中结合《算法4》。
为什么会写这类文章，是因为最近发现自己在结构化思维方面有所爱欠缺，对个人职业发展很有影响。希望通过书写这种方式来改变这种模式
第二个原因也是最近面试其他程序员过程中，问过类似问题，发现对方简单思路都有，但是实际经不起推敲，例如都回答上了这是树的生成，但是对用什么数据结构都没有整体思路。
本系列是用代码来书写，注释中有实现思路。
Go版本算法，只做验证不做说明
思路
1：算法设计条条大路。但是好的数据结构永远是第一步。</br>
2：问题描述
- 输入一列数列，其中每个整数都可以表示一个某种类型的对象。
- 假设P、Q代表两个对象，在实际业务中，可以代表两个对象的ID。
如果相连：</br> - 1：自反性（自己与自己链接，不需要实现）
- 2：对称（也不需要特意声明和实现）
- 3：传递（Q-P Q-R 那么P-R）union主要实现是这个认证。
java版本
/**
* 输入一列数列，其中每个整数都可以表示一个某种类型的对象。
* 假设P、Q代表两个对象，在实际业务中，可以代表两个对象的ID。
* 如果相连：
* 1：自反性（自己与自己链接，不需要实现）
* 2：对称（也不需要特意声明和实现）
* 3：传递（Q-P Q-R 那么P-R）union主要实现是这个认证。
* <p>
* 场景：网络
* 例如社交网路朋友关系等
* 结合我们现在社交电商，可以利用这个算法分析有多少个裂变点，也可以计算某一个人所有相关的裂变，
* 如果判断某一客户反复刷单，就能联通到所有与之相关的黑产。
*
* @author 马晓超
* @date 20180422
*/
public class QuickFind {
//数据结构
private int count;
private int[] uf;
public int size() {
return uf.length;
}
public int[] getUf() {
return uf;
}
//行为抽象
//初始化N个节点
public QuickFind(int N) {
//初始分量数组，N只是模拟1到N的对象，如果用现实中的代替，就是【ID】=地址这种模式。
uf = new int[N];
for (int i = 0; i < N; i++) {
uf[i] = i;
}
count = N;
}
//Find找到这个P所在节点的标记（比如p是人标记就是p的地址）
public int find(int p) {
validate(p);
return uf[p];
}
//判断p,q是否相连
public boolean connected(int p, int q) {
validate(p);
validate(q);
return find(p) == find(q);
}
//联通分量的数量，如果用关系网络来解释，就是有多少个独立的网络。
public int count() {
return count;
}
private void validate(int p) {
int n = uf.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n-1));
}
}
//核心算法union
//
/**
* p 链接 q
* p=3,q=4
* a,b,c,[p],q,e,f,g,h,j
* 连接前 0,1,2,3,4,5,6,7,8,9
* 连接后 0,1,2,4,4,5,6,7,8,9
* <p>
* q，r=2
* 连接前 0,1,2,4,4,5,6,7,8,9
* 连接后 0,1,2,2,2,5,6,7,8,9
*
* @param p
* @param q
*/
public void union(int p, int q) {
if(connected(p,q)){
return;
}
//p address
int pa = find(p);
//q address
int qa = find(q);
//链接一条，就从总数减一条
count--;
//1:循环所有的结点，找出pa的值从注释里示例上就是找出id=3的标记
//2:把pa都编程qa代表他们连到了一起
for (int i = 0; i < uf.length; i++) {
if (uf[i] == pa) {
uf[i] = qa;
}
}
}
public static void main(String[] args) {
//模拟1个节点
QuickFind quickFind = new QuickFind(10);
//3-4链接
quickFind.union(3, 4);
//4-2链接
quickFind.union(4, 2);
//验证
// 总得count应该等于 10-2
if (quickFind.count() != 8) {
throw new RuntimeException("链接分量不正确");
}
//地址2 应该有三个
int i = 0;
for (int j = 0; j < quickFind.size(); j++) {
if (quickFind.getUf()[j] == 2) {
i++;
}
}
if (i != 3) {
throw new RuntimeException("节点数不正确");
}
quickFind.union(8, 3);
quickFind.union(9, 0);
//view Uf
for (int j = 0; j < quickFind.size(); j++) {
System.out.println(quickFind.getUf()[j]);
}
}
}
Go版本
package main
import "fmt"
type QF struct {
Uf []int
Count int
}
//
func (qf *QF) Union(p, q int) {
if qf.connected(p,q) {
return
}
pa := qf.Uf[p]
qa := qf.Uf[q]
for i := 0; i < len(qf.Uf); i++ {
if qf.Uf[i] == pa {
qf.Uf[i] = qa
}
}
qf.Count--
}
func (qf *QF) Init(n int) {
qf.Uf = make([]int, n)
for i := 0; i < n; i++ {
qf.Uf[i] = i
}
qf.Count = n
}
func (qf QF) connected(p, q int) bool {
return qf.Uf[p] == qf.Uf[q]
}
func main() {
qf := new(QF)
qf.Init(10)
qf.Union(3, 4)
qf.Union(4, 9)
fmt.Println(qf.Uf)
fmt.Println(qf.Count)
}
复杂度
O(N）
缺陷
数据规模有限制。实际业务可以适当修改，例如：[uid]=uid,这种模式。
对树的高度，也就是裂变最大层级，放到下篇文章记录。
