最大流问题是图论中一个重要的基础性问题,其求解算法在科学和工程领域以及现实生活中都有广泛的应用,城市交通相关的车流量控制、城市排水管道的最大排水量计算、网络规划、路径规划等重要问题都可以抽象为最大流问题;最大流问题也是计算机视觉、大数据以及图像处理等技术的理论基础。上述技术目前仍在快速发展和更新,因此对最大流问题的深入研究有助于促进相关领域的发展,具有重要的理论意义和实际意义。学术界已提出多种用来解决最大流问题的新算法和新思路,逐步建立了单机求解最大流问题的较为完善的理论体系。虽然现有算法从多个角度求解最大流问题,但在应用到海量图数据处理时仍存在计算结果不准确和求解效率较低等问题。针对这些问题,本文主要研究基于GraphChi框架的大规模图最大流加速,并在该并行图计算框架中尝试解决图分割计算复杂度较高,多次计算存在大量冗余工作等关键问题。本文主要内容如下:(1)研究面向最大流计算的图数据划分和覆盖图构建方法,利用割点构建覆盖图并把原图拆分成多个子图,将割点映射到覆盖图并把其余顶点放入不同的子图。在美国路网等经典数据集上的测试结果表明,该算法将顶点数量缩减到了原图的0.97%~6.64%。(2)研究基于覆盖图的最大流问题映射和拆分方法,给定源点和汇点后在覆盖图中定位对应的两个覆盖图顶点,之后在覆盖图中寻找对应两个顶点之间经过的路径,根据确定的路径找到相应的子图。为提高多子图最大流的计算速度,提出最大流并行加速算法,在本地对路径上的多个子图并行计算最大流。实验结果表明,该算法的最大流计算结果与经典算法高度一致,正确率达到96%以上,且在最大子图上计算最大流能够显著提高计算速度。(3)为进一步加速计算多子图的最大流,提出基于GraphChi框架加速计算方法,把路径上的多个子图提交到GraphChi框架并行计算,并将这些子图的最大流结果整合得到原图中源点和汇点的最大流值。实验结果表明,本文所提出的算法能够将大规模图最大流的计算速度提高到Dinic算法的23~39倍左右,有效降低了时间复杂度,验证了算法的可行性。