严格来讲并查集并不是一个数据结构,而是一个算法,毕竟其英文名直译是联合查找,但作为一个系列,还是当做数据结构讲了。
学术一点讲的话,并查集是用来找一个无向图的联通分量。...有这么一个无向图:
草图 (2).png
这个图结构有三个联通分量[1, 2 ,3, 8], [4,5]和[6, 7]。接下来以此为例分析一下如何使用并查集算法。...之前的例子中每一次union操作两个节点的祖先都不同,所以连通分量数为8-5=3, 如果再添加一个关系[2, 8],2的祖先是8(2->3->8),8的祖先是自己,祖先相同,这个关系在连通分量[1, 2..., 3, 8]中,连通分量数仍为3。...如果在添加一个关系[3, 5],3的祖先是8,5的祖先是5,连通分量数减一为2,而此时parent[8] = 5,parents数组也变为[0, 2, 3, 8, 5, 5, 6, 7, 8],此时的两个连通分量是