摘要:判断有向图上两个顶点之间是否存在一条路径是一个经典问题, 而对于一些路由规划和图分析等实际应用, 要求查找是否存在跳数受限的可达路径, 这是一个变种的图可达查询问题. 对于大图上跳数受限的查询算法, 不仅仅要对大图查询的时间效率和空间效率进行权衡, 而且还要利用跳数受限的特性进行优化. 普通的可达查询算法存在小度数顶点索引项占用空间过多的问题, 造成空间浪费严重. 为此我们提出了一种面向跳数受限的2-hop部分索引方法, 采用改进的索引方法并结合局部搜索, 实现跳数受限的有效可达性查询. 实验结果表明, 在Orkut社交网络数据集上与已有算法相比, 该算法索引空间节省了32%, 同时查询时间略微增加, 使得我们算法可以计算更大规模图的跳数受限可达问题.