计算机科学与探索

作者：苗伟华, 危辉

单位：复旦大学 计算机科学技术学院/软件学院 认知算法模型实验室，上海 200438

关键词：可达性,稀疏图,有向图,强连通,最近公共祖先,位运算

有向图中任意两点间的可达性查询是研究各种网络问题时的一个基础操作，如在社交网络中查询两个人是否相互关注等。但随着网络规模的日益扩大，传统算法因巨大的时间或空间复杂度而变得难以被应用。因此需要根据网络结构特点针对性地使用合适的可达性算法。稀疏图可以看作由若干有向生成树与少量非树边组成，GRKPL算法将稀疏图中的可达性问题拆分成两部分：树上可达性问题与加入非树边后带来的影响。前一部分使用区间标记法解决；后一部分通过构造关键点集，将原图中所有的可达性查询转化为关键点集中的查询后得以解决。关键点集包括所有被非树边覆盖的节点，以及这些节点按照前序遍历的顺序排序后相邻节点之间的最近公共祖先。证明了关键点集的大小与原图中非树边的规模具有相同的数量级。最后在10个中小规模与4个大规模现实数据集上进行了测试，GRKPL在中小规模数据集上表现优异，查询处理时间相较于其他算法平均减少49.8%，空间占用平均减少65.1%。

来源：2023年第10期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2023年第10期