科探空谷
  • Home
  • zhimind home
  • Categories
  • Tags
  • Archives
  • 留学
    • 学校库
    • 专业库
    • 研究方向与招生
    • 工具
    • GPA计算器
    • 脑洞背单词
    • 脱口而出

连通性问题

目录

  • 问题定义:
  • 问题建模:
    • 对象建模:
    • 连通性建模:
    • 连通分量(connected component)
    • 操作的实现:
目录

问题定义:¶

给定 N个物体(点)

存在两种操作:

  1. 连接: 连接两点
  2. 查询连通性: 两点间是否存在路径

问题建模:¶

对象建模:¶

简单就是个点, 然后用个数组下标0 —— N-1来表示

连通性建模:¶

'连接到' 等价于以下数学表示:

  1. 反射: 自身是连通的。
  2. 对称: 如果p连接到q,则q也连接到p
  3. 传递: 如果p连接到q,q又连通r, 则p 也连通r.

连通分量(connected component)¶

相互连通的物体的最大集合

操作的实现:¶

Find查询: 查询两点是否在同一分量 Union连接:


Published

8月 16, 2014

Category

算法

Tags

  • CS 22
  • MOOC 11
  • 算法 6

Stay in Touch

  • Powered by Pelican. Theme: Elegant by Talha Mansoor