Page 365 - 《软件学报》2026年第5期

2244 软件学报 2026 年第 37 卷第 5 期

∗
11. V ← center vertices that v visits in 2ε backward BFS;
12. FOR each u ∈ U , each v ∈ V DO
∗
∗
∗
∗
∗
v
∗
13. IF u can reach in G CI THEN
14. RETURN true;
15. END IF
16. END FOR
17. RETURN false.
例如, 在图 3 所示的图 G 中查询顶点 15 和顶点 3 是否可达, 并且给定 ε=2, 首先判断出这两个顶点不在同一
划分区域, 则由顶点 15 前向广度优先遍历 4 步, 记录下访问到的中心顶点集合 U = {12}, 再由顶点 3 反向广度优
∗
先遍历 4 步, 记录下访问到的中心顶点集合 V = {0,8}, 然后通过图 5 所示的中心索引图 G C 可得到, 顶点 12 不可
I
∗
达顶点 0 和顶点 8, 因此该查询结果为 false. 可达查询算法的时间复杂度最差情况下由两部分构成: 首先从顶点 u
和 v 开始的 2ε 步广度优先遍历消耗的时间为 O(N 2ε (u)+E 2ε (u)), 其中 N 2ε (u) 和 E 2ε (u) 是顶点广度优先遍历 2ε 内访
,
问到的顶点数和边数; 其次在中心索引图中查询是否存在可达的中心顶点对时需消耗的时间为 O(N E CI ) N E CI 为中
心索引图中的总边数. 即最差情况下的时间复杂度为 O(N 2ε (u)+ E 2ε (u)+ N E CI ).
4.2 最短路径查询算法
当给定图 G 和图中的两顶点 u、v 后, 最短路径查询算法同可达查询算法 RQUI 的实现相似, 都是基于统一索
引中的中心索引图 G C 得以加速. 其首先判断顶点 u 和顶点 v 是否在同一划分区域, 若在同一划分区域, 则由顶点
I
u 广度优先遍历 2ε, 在遍历的过程中需记录下遍历的步数, 直到访问到顶点 v 后, 遍历的步数即为要返回的结果
D s (u, v); 若不在同一划分区域, 则先由顶点 u 前向广度优先遍历 2ε 步, 此时有两种情况: (1) 在遍历过程中遇到顶
v, 则直接返回两者的距离 v, 则以 u 和相应
∗
点 D s (u, v). (2) 未遇到顶点 key value 的形式记录下访问到的中心顶点
∗
∗ U , 然后由顶点 v 后向广度优先遍历 v 和相应的步数
∗
的步数 D s (u,u ) 并构成集合 2ε 步, 记录下访问到的中心顶点
∗
∗
∗ ∗ ∗ ∗ D s (u ,v ), 得到
D s (v ,v) 并构成集合 V . 最终通过中心索引图查询集合 U 和集合 V 中可达中心顶点间的最短距离
∗
∗
∗
∗
查询结果 D s (u,v) = min(D s (u,u )+ D s (u ,v )+ D s (v ,v)).
最短路径查询算法 SPUI (shortest path query on unified index) 的流程如算法 3 所示. 可以看出, 其和可达查询
算法相似, 本文不再一一赘述, 最大的不同之处便是最短路径查询算法遍历的同时需记录下遍历的步数以供返回
最终结果. 第 3–10 行讨论顶点 u 和顶点 v 在同一划分区域的情况, 其中在第 4 行记录遍历的步数, 第 6 行将记录
的结果作为最终结果返回. 第 11–15 行讨论顶点 u 和顶点 v 不在同一划分区域的情况, 第 14 行更新最终结果.
算法 3. 最短路径查询算法 SPUI.
输入: 图 G, 顶点 u, 顶点 v, 中心索引图 G CI ;
输出: 顶点 u 和顶点 v 的最短路径距离 D s (u, v).
∗
∗
1. U ← ∅,V ← ∅,dist ← 0,(u,v) ← ∞;
2. IF u, v in the same partition THEN
3. FOR each w that u visits in 2ε steps DO
4. dist ← dist+1;
5. IF w == v THEN
6. D s (u, v) ← dist;
7. END IF
8. END FOR
9. RETURN (u, v);