《表3 图G1'的2-hop标签索引Tab.3 The 2-hop label index of G1'》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《一种基于悬挂顶点关联索引的最短路径查询算法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

2) 构建2-hop标签索引H。对图G1&apos；中的顶点按照度由大到小进行排序的结果为{v0，v1，v2，v3，v4，v5}，然后依次把每个顶点v作为起始点对图遍历:当把v0作为起始点进行图遍历时，把v0放入队列Q中，距离数组d中d[v0]=0，其他元素的值为无穷。队列Q中有一个元素v0，队列不为空，队头v0出队列并赋给u，此时QUERY（v，u，H&apos；）=∞，d[u]=0，则向H（v0）标签中添加二元组（v0，0），同时把v0未访问的邻接点v1、v2和v4加入到队列Q中，并把d[v1]、d[v2]、d[v4]的值更新为1，即v0到这3个顶点的最短距离为1。然后继续判断下一个顶点v1，此时队列Q仍不为空，队头v1出队列并赋给u，此时QUERY（v0，v1，H&apos；）=∞和d[v1]=1，则向H（v1）中添加二元组（v0，1），同时把v1未访问的邻接点v3加入到队列Q中，并把d[v3]的值更新为2，继续循环处理v2、v3、v4和v5直到循环的条件不满足为止，此时把顶点v0作为起始点遍历图的过程结束。同理，可以对顶点v1、v2、v3、v4和v5分别作为起始点对图进行遍历操作。当所有顶点都进行一次图遍历操作后，就可以得到数据图G1&apos；的2-hop标签索引如表3所示。