k跳可达性查询是图可达性查询问题的一般形式,在社交网络和传感器网络领域有很重要的应用。随着图数据的规模不断扩大,大图中的可达性查询问题受到了越来越多的关注。传统的可达性查询算法不能有效地支持大图上的可达性查询,而一些具有扩展性的可达性查询算法由于索引中缺乏距离信息,在查询过程中不能有效地通过索引判断那些具有可达性但是不具有k跳可达性的顶点对,因而应用于大图上的k跳可达性查询时,不能达到k跳可达性查询算法的及时性要求。为了提高算法的扩展性,根据k跳可达性查询的特点,将具有扩展性的可达性查询索引与广度优先遍历得到的距离索引结合起来完成查询,从而减少在线搜索的搜索空间,提高了算法的查询效率。其中,系统的索引构造结合了FELINE索引、BFSI索引两种关键索引技术。主要研究内容包括,提出基于广度优先树的BFSI索引的构建方法,通过生成广度优先树的区间索引来记录部分顶点的距离信息;针对现实图中存在的power-law分布,提出了一种新的广度优先树的构造方法BFSI-S,相比于基于根节点构建的广度优先树,可以有效提高索引算法的覆盖率。然后根据图的入度和出度的差异,提出了针对逆向图的BFSI-B索引,结合双向搜索的方法,进行双向剪枝,大大提高了剪枝的效率。在大量具有不同特征的有向无环图中,对k跳可达性查询算法进行了详细的测试。测试结果表明,相比于传统的k跳可达性查询方法,在相同的硬件条件下,能够支持更大规模图的k跳可达性查询,索引大小和查询时间都优于最新的scalable k-reach方法。算法具有良好的扩展性和时间效率,能够适应大图上的k跳可达性查询的要求。