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

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

4. <node, dist>← BL(k i ).pop;
5. dist j ← ∞(1 ⩽ j ⩽ m), dist i ← dist, newr ←< ∅,(∅,∅,...,∅) >, newr i ← node;
6. IF dist ≥ t THEN
7. RETURN t;
8. END IF
9. FOR j ∈ [1,m] and j , i DO
10. FOR each u ∈ Node(k j ) DO
11. IF dist j > SPUI(node, u) THEN
12. dist j ← SPUI(node, u), newr j ← u;
13. END IF
14. END FOR
15. END FOR
∑
m
16. IF dist j < t THEN
j=1
∑ m
17. r root ← node, t ← dist j , r ← newr
j=1
18. END IF
19. visited(node) ← true;
20. FOR each v that node visits in 1 backward DO
21. IF visited(v) == false THEN
22. BL(k i ).push(v, dist+1);
23. END IF
24. END FOR
25. END WHILE
26. RETURN t.
例如, 给定图 3 所示的图 G 和查询的关键字组 q k =(d, e, h), 各关键字的顶点集合和后向搜索列表 BL(e) 的更
新过程如图 7 所示. 查询时, 首先获取后向搜索列表 BL(e) 的头元素 (7, 0), 计算出顶点 7 到关键字 d 和 h 的距离,
∑ 3
得到评价函数 dist i = D s (7,7)+ D s (7,3)+ D s (7,7) = 2; 然后将顶点 7 后向遍历一步可以访问到的新顶点 2 添加
i=1
到后向搜索列表 BL(e) 中, 即添加元素 (2, 1), 并将头元素 (7, 0) 从列表中删除; 接着获取头元素 (8, 0) 后, 得到顶
∑ 3
点 8 评价函数 dist i = D s (8,11)+ D s (8,8)+ D s (8,3) = 5, 不优于当前的评价函数, 不需更新最优结果树; 如此反
i=1
复遍历后向搜索列表 BL(e), 直到获取头元素 (0, 2) 后, 此时 dist 值已经大于等于当前最优评价函数, 因此可以终止
本次查询, 并返回最优结果 t=<7, (7, 3, 7)>.

Node(d)={7,16,1,11}
Node(e)={7,8,9}
Node(h)={3,4,12,15,16,5} BL(e): (7, 0) (8, 0) (9, 0)

(a) 顶点集合 (b) 后向搜索列表
图 7 顶点集合与后向搜索列表

当给定图 G 和一组关键字 q k =(k 1 , k 2 ,…, k m ) 后, 关键字查询算法的时间主要用于遍历后向搜索列表 BL(k i ) 中
的元素, 每访问到一个新顶点 u 时, 需要消耗 m · (O(N 2ε (u)+E 2ε (u))+O( N E CI )) 去查询到其他关键字的最短距离, 其
中 m 为关键字的个数. 最差情况下, 需遍历图 G 中全部的顶点, 即时间复杂度为 N V · m · (O(N 2ε (u)+E 2ε (u))+O( )),
N E CI
其中 N V 为数据图 G 中的顶点总数, 但实际情况访问到的顶点个数要远小于 N V .