简单描述：给出N个点，给出M中连接关系，根据连接关系（点点对）对N个点进行处理：如果两点之间没有直接或间接的连接关系，则连接；如果有，则跳过。最终所有的点将被划分为几个连通分量。
通过该例子说明算法分析的基本步骤：
- 完整而详细地定义问题，找出解决问题所必须的基本抽象操作并定义一份API；
- 简洁的实现一种初级算法，给出一个精心组织的开发用例并使用实际数据作为输入；
- 分析初级算法能够解决的问题的最大规模
- 改进实现，通过经验性分析和数学分析验证改进后的效果；
- 用更高层次的抽象表示数据结构或算法来设计更高级的改进版本；
- 为最坏情况下的性能提供保证，同时分析平均情况下的性能；
- 深入研究...
代码的细节问题:
- 改进实现可以采用子类继承父类的方式实现，覆盖重写find和union方法；
- 子类不能访问父类的私有成员变量，因此需要重新定义子类的成员变量；
- 为了代码简洁，子类的构造方法可以调用父类的构造方法；
- 数组在构造方法中的初始化问题，不要创建成局部变量。
GitHub链接：https://github.com/SparkCool/Algorithm4th/tree/master/A01Fundamental/A0104_UnionFind
网友评论