一种基于2-Hop Labeling的进化图上可达性的快速查询方法

本发明涉及一种基于2‑Hop Labeling的进化图上可达性的快速查询方法，该方法包括以下步骤：1)对原始图进行预处理，采用Tarjan算法对每个时间片上的图中节点进行强连通分量划分，将原始图转化为由强连通分量表示的简化图结构；2)构建包含强连通分量时效表和2‑Hop Labeling可达性标签的索引；设计并构建强连通分量时效表的数据结构，用于存储强连通分量与原始图节点的对应关系，同时记录强连通分量内部节点的可达性信息；结合强连通分量时效表设计2‑Hop Labeling可达性标签的数据结构，构建完整的索引结构，用以存储和查询图中节点之间的可达性关系；3)设计基于索引的可达性快速查询方法，利用强连通分量时效表和2‑Hop Labeling可达性标签，至多合并两跳信息，实现快速可达性查询。