带权大图上的K步可达性查询算法

可达性查询作为图中最常用的基本操作,在生物信息学、智慧交通等领域应用广泛,但在一些现实问题中,仅仅进行可达性查询并不能满足人们对距离信息的需求,K步可达性查询应运而生。目前已有的K步可达性查询的处理对象为有向无环图,无法充分反映顶点间的距离信息,并且无环图并不符合交通网络等实际应用情况。针对以上问题,提出一种针对带权有向图的K步可达性查询算法。通过求解近似最小顶点覆盖集,分别构建了顶点覆盖集内索引和顶点覆盖集外的双向最短路径索引,有效避免了查询时的I/O操作,提高了查询效率。在10个数据集上进行对比实验,并通过比较索引构建时间、索引规模、查询时间等指标证明了该算法的高效性。