面向大规模图计算的连通分量算法分析与优化.

In recent years, graph computing has played an increasingly important role in many fields. The connected component algorithm is an important basic algorithm for graph computing, which can be applied to multiple scenarios such as reachability query. This paper is oriented to the large-scale graph traversal GraphSOO standard test, and optimizes the connected component algorithm and data structure. The main innovations are as follows: (1) A shortcutting-vector algorithm is proposed for the union-find set, and the degree of coordination between the algorithm and the data structure is tested. (2) The multi-threaded iterative rotation algorithm is used to achieve the parallel acceleration of the algorithm. (3) The advantages and disadvantages of different implementation methods are compared from multiple dimensions. Based on the optimization method, the performance is evaluated and analyzed. When scale = 25 (including 225 vertices), the speedup ratio of the shortcutting-vector algorithm to the rank-merging algorithm based on two-dimensional vectors and linked lists is 1. 38 times and 1. 40 times, respectively. The speedup ratios of BFS and DFS are 4. 76 times and 4. 70 times respectively, and the space occupation is 4. 1%〜4. 6% of the two algorithms. In addition, the speedup ratio of parallel to serial is 1. 57 times. [ABSTRACT FROM AUTHOR]