union-find, quick-union, weighted-quick-union

[barretlee]

union-find, quick-union, weighted-quick-union

[barretlee]

动态联通图问题，需要将问题抽象成一个可编程的过程。书中提到触点、分量和连接，所以编程第一步，先初始化触点信息，简洁期间，每个触点信息保持跟他们的序号一样就行了。

• union find，大致意思就是将所有联通的节点信息归并为一个，有点类似于物理电路中的电势，让各点电势一样；
• quick union，将联通的两点按照顺序连接起来，有点像指针，a->b->c->d，保持串联，每次新的连接，都去判断两点的根指针是否一致，如果一致则略过，如果不一致则连接；
• weighted quick union，在上面算法的基础上，添加了权重判断，每个节点除了序号信息外，还有一个数深度信息（size），当指针不一致需要连接时，将深度小的数合并到大的上面（我觉得这一步有点难理解）。

研究算法的实现还是挺有意思的，最难的地方莫过于对复杂度的计算和判断。