第40卷第7期计算机应用与软件Vol40No.72023年7月ComputerApplicationsandSoftwareJul.2023带权大图上的K步可达性查询算法李文华李盛恩(山东建筑大学计算机科学与技术学院山东济南250100)收稿日期:2020-08-28。李文华,硕士生,主研领域:图数据管理。李盛恩,教授。摘要可达性查询作为图中最常用的基本操作,在生物信息学、智慧交通等领域应用广泛,但在一些现实问题中,仅仅进行可达性查询并不能满足人们对距离信息的需求,K步可达性查询应运而生。目前已有的K步可达性查询的处理对象为有向无环图,无法充分反映顶点间的距离信息,并且无环图并不符合交通网络等实际应用情况。针对以上问题,提出一种针对带权有向图的K步可达性查询算法。通过求解近似最小顶点覆盖集,分别构建了顶点覆盖集内索引和顶点覆盖集外的双向最短路径索引,有效避免了查询时的I/O操作,提高了查询效率。在10个数据集上进行对比实验,并通过比较索引构建时间、索引规模、查询时间等指标证明了该算法的高效性。关键词带权大图K步可达性顶点覆盖图数据库知识图谱中图分类号TP301文献标志码ADOI:10.3969/j.issn.1000386x.2023.07.005KHOPREACHABILITYQUERIESONWEIGHTEDLARGEGRAPHSLiWenhuaLiSheng’en(SchoolofComputerScienceandTechnology,ShandongJianzhuUniversity,Jinan250100,Shandong,China)AbstractReachabilityqueryisoneofthebasicandcommonusedoperationingraphdataandwidelyusedinbioinformatics,intelligenttransportationandsoon.However,insomepracticalproblems,thereachabilityqueryalonecannotmeetpeoplesdemandfordistanceinformation,sothekhopreachabilityqueryarises.Atpresent,theprocessingobjectofthe...