谢 羿（沈阳黎明航空发动机（集团）有限责任公司，辽宁 沈阳 110043）



基于BFS结果集的可达性保持图并行计算

谢 羿
（沈阳黎明航空发动机（集团）有限责任公司，辽宁 沈阳 110043）

摘 要：传统计算可达性保持图的方法通常基于单机模式，针对小规模数据集进行计算。在处理大规模图数据以及大量中间数据时，传统方法将面临内存容量和计算速度的瓶颈问题。为了解决上述问题，本文提出了基于BFS结果集的可达性保持图并行计算方法。

关键词：图数据；可达；MapReduce；并行化；保持图

0 引言

可达性保持图实质上是一种在可达性查询方面与原始图等价的压缩图。其目的是获取可达性保持图，以解决直接基于原始图进行可达性查询开销过大的问题。算法首先使用广度优先遍历（BFS）获得原始图中每个顶点的所有祖先顶点和后代顶点，然后通过基于类似邻居匹配的方法匹配原始图中各顶点的祖先顶点集和后代顶点集来寻找等价类，并对等价类进行压缩处理。

1 基于BFS结果集的可达性保持图并行计算

1.1 基于BFS结果集的SCC并行查找算法

定理1：强连通分量内的任意两顶点相互可达。

根据定理1，我们可以推出：对于某一强连通分量SCC内的任意一个顶点v，SCC中除v之外的其他顶点既包含于v的向后BFS结果集N-，又包含于v的向前BFS结果集N+。本文不考虑单一顶点作为强连通分量进行处理，对于可达性等价类的处理同样也不考虑将单一顶点作为等价类处理。基于BFS结果集的SCC查找算法如下：

（1）输入每个顶点v的向后BFS结果集N-和向前BFS结果集N+；……