基于并查集的六度分隔理论的验证与实现

(数据科学学习手札104)Python+Dash快速web应用开发——回调交互篇(上)

首发于微信公众号:几何思维

1.六度分隔理论

世界上任何两个互不相识的人,最多只需要通过6个中间人,就可以建立联系。
哈佛大学的社会心理学家米尔格兰姆于1967设计了一个连锁信件实验。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的160个人,信中放了一个波士顿股票经纪人的名字,并要求每名收信人把这封信寄给自己认为是比较接近这名股票经纪人的朋友。这位朋友收到信后,再把信寄给他认为更接近这名股票经纪人的朋友。最终,大部分信件都寄到了这名股票经纪人手中,每封信平均经手6次到达。

例如你认识老王,老王认识李大爷,李大爷又认识某人,如此关联,你和奥巴马之间,最多只差6个人介绍就可以加微信好友啦。

2.引发思考

如果我现在知道了所有人的通讯录好友,我想知道我到底能不能认识老奥,怎么验证呢?
全球有77亿人口,每个人的好友圈也有几百上千,这样的数据量是很大的,简单的一个一个的查找是行不通的。

那么问题来了,人口普查哪家强,四川成都找老王。。。
所有的信息数据如下表:

转换成图的形式会比较直观。如果把2个互相认识的人用线连接起来,问题就转化成:你和老奥之间能否找到一条通路(暂不考虑最短是不是不超过6个人)。

3.问题建模

假设朋友的朋友都是朋友,朋友的敌人也是朋友(或者敌人的朋友还是朋友,whatever…)。

我们把所有直接认识的,或者能间接认识的都放到一个大集合中,建立一个大朋友圈。
问题就变成:老奥在不在我们的大朋友圈里?

如果你的大朋友圈里面有人认识川普,那就要把川普的朋友圈里面的所有人都加进来,形成一个新的朋友圈。

小白的经典CNN复现(二):LeNet-5

相信敏锐的你已经发现问题的本质,这里面只有2个重要的操作,来跟我一起大声朗读,并…查…。这就需要一种能高效处理集合的合并与查找的算法,并查集就是专门为这种场景量身定制。

4.算法理论

并查集本质是一个森林,里面有很多树。

每个树有一个根,以不同的根代表不同的集合。如下,root1,root2代表两个集合。

初始时,每个元素都属于一个独立的集合,该元素作为根。每个根指向一个虚拟根-n,代表权重(表示该集合有n个元素)。
更新合并
将权重小的集合的根指向权重大的集合的根(此操作是为尽量降低树的深度)。

查找
判断2个元素是否属同一集合,只需向上查找根,再判断是否相同。
过程中做路径压缩,加快下一次查找速度。

5.代码实现

查找

int findFather(int s) {
    int root = s, temp;
    // 查找s的最顶层根
    while (father[root] >= 0) {
        root = father[root];
    }
    // 路径压缩,提高后续查找效率
    while (s != root) {
        temp = father[s];
        father[s] = root;
        s = temp;
    }
    return root;
}

合并

void unionSet(int s, int e) {
    int rootS = findFather(s);
    int rootE = findFather(e);
    int weight = father[rootS] + father[rootE];
    // 将结点数少的集合作为结点数多的集合的儿子节点
    if (father[rootS] > father[rootE]) {
        father[rootS] = rootE;
        father[rootE] = weight;
    } else {
        father[rootE] = rootS;
        father[rootS] = weight;
    }
}

例题,poj1182,poj1308,poj1456,poj1611

扫描下方二维码关注公众号,第一时间获取更新信息!

基于.NET Core的优秀开源项目合集

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

Jmeter二次开发——自定义函数

2021-1-22 18:26:00

经验教程

(数据科学学习手札104)Python+Dash快速web应用开发——回调交互篇(上)

2021-1-22 19:57:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索