随着信息技术的发展,越来越多的数据以图的形式存在,如社交网络、生物信息学和电子商务等领域中大量的信息都可以用图来表示和建模。作为一种特殊的数据类型,图数据有着许多鲜明的特征,如数据规模大、拓扑结构复杂、计算复杂度高等特点,图上的查询处理难度比传统数据类型(如关系型数据表、XML数据等)上的查询处理难度大得多。在图数据分析领域,基本问题之一就是研究图中两个结点之间的关系,例如结点A如何影响另一个结点B,A和B两种物质的相互作用链以及A和B两者之间的关系网等等,解决上述问题的关键点之一就是两点间的路径枚举问题。因此,本文对k跳s-t路径枚举问题进行深入研究,该问题旨在找出图中从起始结点s到终止结点t之间k跳内可达的所有简单路径。解决k跳s-t路径枚举问题的主要障碍在于,s-t路径的数目往往随着跳数的增加呈指数型增长,即使对于很小的k值,所涉及的搜索空间都很大,简单地基于复制和循环枚举所有的s-t路径,存在响应时间过长和内存占用率高等诸多用户难以接受的问题。针对目前路径枚举算法中存在的不足,本文研究并提出了多重图上路径枚举中的关系优化方案以及两种大规模多重图上k跳内可达的s-t路径枚举方案,即P-DFS和HPP-DFS。多重图上路径枚举中的关系优化方案旨在降低图的复杂度。本文对大规模多重图进行合理组织,针对给定的结点s和t,跳数约束k,对图进一步缩减,提前删除一些不可能出现在结果集中的结点和边,减少s-t路径枚举时的IO开销以及搜索空间,提高查询效率。P-DFS是一种基于深度优先搜索求解k跳s-t路径枚举问题的方法,该算法的核心思想为“尽早终止递归,避免徒劳尝试”。在路径枚举过程中,利用已求得的当前结点距离终止结点t的最短路径长度,进行适当地剪枝,尽可能保证每次迭代生成的中间路径至少包含在一条有效路径中,降低时间复杂度。HPP-DFS的核心思想为“利用前期查询结果,避免二次多余计算”。在现实世界中,图中结点的度数分布不均匀,有的结点出度(入度)很大,有的结点出度(入度)则很小,P-DFS在查询路径时采取逐一枚举k跳s-t路径的方案,没有有效利用前期已经计算过的路径信息,在查询过程中遇到度数较大的结点时,访问的边的数量会迅速增加,极有可能存在大量重复的计算,因此在设计HPP-DFS时,通过共享包含热点的路径中部分中间路径的计算结果,进一步缩短查询响应时间。从理论上讲,本文证明了P-DFS和HPP-DFS为多项式时间内可解的算法,其中,每输出一条有效路径的时间复杂度为0(km)。本文结合多重图上路径枚举中的关系优化方案,在真实数据集上进行大量对比实验,结果表明本文提出的k跳s-t路径枚举方案P-DFS和HPP-DFS查询效率很高,具有高可行性和和高准确性。