问题定义:¶
给定 N个物体(点)
存在两种操作:
- 连接: 连接两点
- 查询连通性: 两点间是否存在路径
问题建模:¶
对象建模:¶
简单就是个点, 然后用个数组下标0 —— N-1来表示
连通性建模:¶
'连接到' 等价于以下数学表示:
- 反射: 自身是连通的。
- 对称: 如果p连接到q,则q也连接到p
- 传递: 如果p连接到q,q又连通r, 则p 也连通r.
连通分量(connected component)¶
相互连通的物体的最大集合
操作的实现:¶
Find查询: 查询两点是否在同一分量 Union连接: