第４０卷第７期计算机应用与软件Ｖｏｌ４０Ｎｏ．７２０２３年７月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＪｕｌ．２０２３带权大图上的Ｋ步可达性查询算法李文华李盛恩（山东建筑大学计算机科学与技术学院山东济南２５０１００）收稿日期：２０２０－０８－２８。李文华，硕士生，主研领域：图数据管理。李盛恩，教授。摘要可达性查询作为图中最常用的基本操作，在生物信息学、智慧交通等领域应用广泛，但在一些现实问题中，仅仅进行可达性查询并不能满足人们对距离信息的需求，Ｋ步可达性查询应运而生。目前已有的Ｋ步可达性查询的处理对象为有向无环图，无法充分反映顶点间的距离信息，并且无环图并不符合交通网络等实际应用情况。针对以上问题，提出一种针对带权有向图的Ｋ步可达性查询算法。通过求解近似最小顶点覆盖集，分别构建了顶点覆盖集内索引和顶点覆盖集外的双向最短路径索引，有效避免了查询时的Ｉ／Ｏ操作，提高了查询效率。在１０个数据集上进行对比实验，并通过比较索引构建时间、索引规模、查询时间等指标证明了该算法的高效性。关键词带权大图Ｋ步可达性顶点覆盖图数据库知识图谱中图分类号ＴＰ３０１文献标志码ＡＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０２３．０７．００５ＫＨＯＰＲＥＡＣＨＡＢＩＬＩＴＹＱＵＥＲＩＥＳＯＮＷＥＩＧＨＴＥＤＬＡＲＧＥＧＲＡＰＨＳＬｉＷｅｎｈｕａＬｉＳｈｅｎｇ’ｅｎ（ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＳｈａｎｄｏｎｇＪｉａｎｚｈｕＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５０１００，Ｓｈａｎｄｏｎｇ，Ｃｈｉｎａ）ＡｂｓｔｒａｃｔＲｅａｃｈａｂｉｌｉｔｙｑｕｅｒｙｉｓｏｎｅｏｆｔｈｅｂａｓｉｃａｎｄｃｏｍｍｏｎｕｓｅｄｏｐｅｒａｔｉｏｎｉｎｇｒａｐｈｄａｔａａｎｄｗｉｄｅｌｙｕｓｅｄｉｎｂｉｏｉｎｆｏｒｍａｔｉｃｓ，ｉｎｔｅｌｌｉｇｅｎｔｔｒａｎｓｐｏｒｔａｔｉｏｎａｎｄｓｏｏｎ．Ｈｏｗｅｖｅｒ，ｉｎｓｏｍｅｐｒａｃｔｉｃａｌｐｒｏｂｌｅｍｓ，ｔｈｅｒｅａｃｈａｂｉｌｉｔｙｑｕｅｒｙａｌｏｎｅｃａｎｎｏｔｍｅｅｔｐｅｏｐｌｅｓｄｅｍａｎｄｆｏｒｄｉｓｔａｎｃｅｉｎｆｏｒｍａｔｉｏｎ，ｓｏｔｈｅｋｈｏｐｒｅａｃｈａｂｉｌｉｔｙｑｕｅｒｙａｒｉｓｅｓ．Ａｔｐｒｅｓｅｎｔ，ｔｈｅｐｒｏｃｅｓｓｉｎｇｏｂｊｅｃｔｏｆｔｈｅ...
