基于数组型并查集的连通域标记算法

Labeling Connected Components Algorithm Based on Array of Union-Find

常用的二次扫描算法存在某些缺陷,即共同连通域的合并主要是通过重复遍历共同连通域标号数组,修改相应的共同连通域标号完成的.重复遍历严重影响算法的性能.数组型并查集算法利用树型数据结构特点实现连通域合并,以取代重复遍历.实验表明数组型并查集算法更具优势.

The usual two scans algorithms has some defects that common connected components are mainly merged via repeating to scan the label array of common connected components, and modifying relevant field of the array. The way seriously affects the performance of the algorithm. The algorithm based on array of union-find, which makes full use of the specialty of tree data structure to merge common connected components, can instead of the repeating scans. The experiments show that the algorithm based on array of union-find has more advantages than the algorithm which repeats to scan the label array of common connected components.