作者 | 科学眼光看世界责编 | 张文
头图|CSDN 下载自视觉中国
出品 | CSDN（ID：）
文章插图
六度分隔理论
世界上任何两个互不相识的人 ， 最多只需要通过 6 个中间人 ， 就可以建立联系 。
哈佛大学的社会心理学家米尔格兰姆于 1967 设计了一个连锁信件实验 。他将一套连锁信件随机发送给居住在内布拉斯加州奥马哈的 160 个人 ， 信中放了一个波士顿股票经纪人的名字 ， 并要求每名收信人把这封信寄给自己认为是比较接近这名股票经纪人的朋友 。这位朋友收到信后 ， 再把信寄给他认为更接近这名股票经纪人的朋友 。最终 ， 大部分信件都寄到了这名股票经纪人手中 ， 每封信平均经手 6 次到达 。
例如你认识老王 ， 老王认识李大爷 ， 李大爷又认识某人 ， 如此关联 ， 你和奥巴马之间 ， 最多只差 6 个人介绍就可以加微信好友啦 。
文章插图
引发思考
如果我现在知道了所有人的通讯录好友 ， 我想知道我到底能不能认识老奥 ， 怎么验证呢？
全球有 77 亿人口 ， 每个人的好友圈也有几百上千 ， 这样的数据量是很大的 ， 简单的一个一个的查找是行不通的 。
【通过 6 人介绍可以认识世界上任何一个人？】
文章插图
那么问题来了 ， 人口普查哪家强 ， 四川成都找老王 。。。
所有的信息数据如下表：
文章插图
文章插图
转换成图的形式会比较直观 。如果把2个互相认识的人用线连接起来 ， 问题就转化成：你和老奥之间能否找到一条通路（暂不考虑最短是不是不超过 6 个人） 。
文章插图
问题建模
假设朋友的朋友都是朋友 ， 朋友的敌人也是朋友(或者敌人的朋友还是朋友 ， ...) 。
我们把所有直接认识的 ， 或者能间接认识的都放到一个大集合中 ， 建立一个大朋友圈 。
问题就变成：老奥在不在我们的大朋友圈里？
文章插图
如果你的大朋友圈里面有人认识川普 ， 那就要把川普的朋友圈里面的所有人都加进来 ， 形成一个新的朋友圈 。
文章插图
相信敏锐的你已经发现问题的本质 ， 这里面只有 2 个重要的操作 ， 来跟我一起大声朗读 ， 并...查... 。这就需要一种能高效处理集合的合并与查找的算法 ， 并查集就是专门为这种场景量身定制 。
文章插图
算法理论
并查集本质是一个森林 ， 里面有很多树 。
每个树有一个根 ， 以不同的根代表不同的集合 。如下 ， root1 ， root2代表两个集合 。
文章插图
如初始时 ， 每个元素都属于一个独立的集合 ， 该元素作为根 。每个根指向一个虚拟根-n ， 代表权重(表示该集合有 n 个元素) 。
- 电子地图、地理信息系统 专业的GIS开发引擎介绍
- 个人理解总结 Linux系统编程之进程
- Waymo无人车正在学习遇到警车/消防车/救护车怎么办
- 黄瓜细菌性角斑病该如何防治？
- 核电站反应堆技术与原理
- 一些常见花卉的寓意介绍
- 12306超过5个人怎么买
- 29-基于stm32单片机智能红外计数器人流量统计程序原理图PCB元件清单
- 教装o的alpha做个人 教装o的alpha做个人补车
- 29