首页 > 代码库 > 普林斯顿公开课 算法1-11:并查集的应用
普林斯顿公开课 算法1-11:并查集的应用
应用
渗透问题
游戏中会用到。
动态连接
- 近期共同祖先
- 等价有限状态机
- 物理学Hoshen-Kopelman算法:就是对网格中的像素进行分块
- Hinley-Milner多态类型判断
- Kruskai最小生成树
- Fortran等价语句编译
- 形态学开闭属性
- Matlab中关于图像处理的bwlabel函数
渗透问题
一个N×N的矩阵,推断顶部和底部是否连通就是渗透问题。
下图中左側的矩阵能渗透,右側矩阵不能渗透。
渗透问题在电学、流体力学、社会交际中都有应用。
在游戏中可能须要生成一张地图,可是作为地图肯定是须要连通的。那么怎样保证生成的地图一定是连通的呢?下图展示了地图生成的过程,白点表示可以到达的地方,黑点表示障碍物,蓝点表示可以连通的地方。生成地图的时候就是不断添加白点,直到上下可以连通为止。
为了推断是否能渗透,计算的过程中会添加一个虚拟的节点,这样就把渗透问题简化成推断两个节点是否能连通。下图展示了虚拟节点示意图。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。