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

陈迪 等: 大图数据的统一查询处理机制 2241

1. P ← ∅, C ← ∅, IN ← ∅, OUT ← ∅;
2. Q ← all nodes in G sorted by degree;
3. WHILE Q is not empty DO
4. u ← Q.pop();
5. C.push(u), P i .push(u);
6. FOR each v that u can visit in ε distance DO
7. IF v ∈ Q THEN
8. P i .push(v), Q.remove(v);
9. END IF
10. END FOR
11. P.push(P i );
12. END WHILE
13. OUT, IN ← get important points of every parts;
14. RETURN P, C, IN, OUT.
算法 1 中, 第 13 行遍历图 G 并提取出重要顶点的过程为: 得到近优划分覆盖 P 后, 逐一遍历每一划分区域
P i 中的顶点 v, 根据当前顶点 v 的入度和出度以及相应的边, 判断顶点 v 是否属于出边界顶点集合或入边界顶点集
合. 若顶点 v 入度大于 0 且存在属于其他划分区域的入顶点, 则将顶点 v 添加到该划分区域 P i 的入边界顶点集合
IN i 中, 同理若顶点 v 出度大于 0 且存在属于其他划分区域的出顶点, 则将顶点 v 添加到该划分区域 P i 出边界顶点
集合 OUT i 中. 待所有划分区域都被遍历过后, 便提取出所有的重要顶点, 即 OUT 为 OUT i 的集合, IN 为 IN i 的集合.
例如, 给定如图 3 所示的图 G, 并给定 ε = 4, 为得到近优划分, 首先将图中顶点按照度排序得到{8, 12, 0, 3, 5,
1, 2, 4, 7, 9, 10, 6, 11, 13, 14, 15, 16, 17}, 从顶点 8 开始前向遍历并后向遍历距离 4 以内, 可得到以顶点 8 为中心顶
点的划分区域 P 1 为{8, 3, 4, 14, 9, 10, 2, 7}. 需注意顶点 3 已经属于划分区域 P 1 , 应从排序队列中移除. 接着分别从
顶点 12, 顶点 0 和顶点 5 开始遍历, 得到了如图 4 所示的图数据 G 的近优划分覆盖, 虚线框住的为一个划分区域,
共有 4 个划分区域 P 1 、P 2 、P 3 和 P 4 , 并得到中心顶点集合 C, 各划分区域中边框加粗的顶点为该划分区域的中心
顶点, 即中心顶点集合 C={8, 12, 0, 5}.

17 {a}
4
P 3
0 {a, b, c}
4
5
{b, d} 1 2 {a, c}
{h} 4 2
1 2
1 3
7 {d, e}
2 1 13 {i}
{c, h, g} 5 {h, f}
{h, i} 1 P 2
4 3 8 {e, f, g}
P 4 2
11 6 3 1 12 16 {d, h}
{d, g} {c} 3
14 9 2 2
P 1 15 {h}
{f, i} {e} 10
{f}
图 4 近优划分覆盖

在得到近优划分覆盖后, 逐一去遍历各划分区域中的顶点, 例如在遍历划分区域 P 1 时, 顶点 3 的入度为 2, 并
且其入顶点 1 属于其他划分区域, 则顶点 3 为入边界顶点. 遍历完各划分区域后, 得到了图 G 的出边界顶点集合 OUT