针对目标生成树查询的图数据压缩方法及装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN109885733A(43)申请公布日2019.06.14(21)申请号201910048119.9(22)申请日2019.01.18(71)申请人清华大学地址100084北京市海淀区清华园北京100084-82信箱(72)发明人李超张桂刚宋克禹张勇邢春晓(74)专利代理机构北京路浩知识产权代理有限公司11002代理人王莹李相雨(51)Int.Cl.G06F16/901(2019.01)G06F16/903(2019.01)权利要求书2页说明书8页附图7页(54)发明名称针对目标生成树查询的图数据压缩方法及装置(57)摘要本发明实施例提供针对目标生成树查询的图数据压缩方法及装置，方法包括：输入待压缩的图，包含结点、边和边的权值；初始化生成树覆盖子图(只包含待压缩的图中的结点、不包含待压缩的图中的边)，在生成树覆盖子图上建立并查集存储连通块信息；将待压缩的图中所有边按权值预设顺序排序存入一个队列；遍历队列中所有权值为预设值的边，对于权值为预设值的所有边中任一边，判断边的端点是否在并查集中同一连通块中，若是则标记为树外边；将已遍历过的边移出队列加入生成树覆盖子图并维护并查集；在队列为空时删除待压缩的图中所有标记为树外边的边。可在保证原图中所有目标生成树被保留前提下删除所有树外边，减小存储图数据的空间消耗，实现压缩。CN109885733ACN109885733A权利要求书1/2页1.一种针对目标生成树查询的图数据压缩方法，其特征在于，包括：输入待压缩的图，所述图中包含结点、边和目标生成树查询所依赖的边的权值；初始化生成树覆盖子图，初始化的生成树覆盖子图只包含所述待压缩的图中的结点、不包含所述待压缩的图中的边，并在所述生成树覆盖子图上建立并查集，所述并查集存储所述生成树覆盖子图内的连通块信息；将所述待压缩的图中所有的边，按照权值的预设顺序进行排序，存入一个队列中；遍历所述队列中所有权值为预设值的边，对于所述队列中所有权值为预设值的边中的任一边，判断所述边的端点是否在所述并查集中的同一连通块中，若是则将所述边标记为树外边；将所述队列中已经遍历过的边移出所述队列，加入所述生成树覆盖子图，并维护加入边之后的生成树覆盖子图上的并查集；判断所述队列是否为空，若是，则将所述待压缩的图中所有标记为树外边的边删除，输出删除树外边后压缩完毕的图。2.根据权利要求1所述的方法，其特征在于，在判断所述队列是否为空之后，所述方法还包括：若所述队列不为空，则返回所述遍历所述队列中所有权值为预设值的边，对于所述队列中所有权值为预设值的边中的任一边，判断所述边的端点是否在所述并查集中的同一连通块中，若是则将所述边标记为树外边的步骤。3.根据权利要求1所述的方法，其特征在于，所述维护加入边之后的生成树覆盖子图上的并查集，包括：对于生成树覆盖子图中新加入的边，将每条新加入的边的两个端点在并查集中所属的集合进行合并。4.根据权利要求1所述的方法，其特征在于，所述目标生成树，包括：最小生成树或最大生成树。5.根据权利要求4所述的方法，其特征在于，若所述目标生成树为最小生成树，则所述按照权值的预设顺序为按照权值由小到大，所述预设值为最小值。6.根据权利要求4所述的方法，其特征在于，若所述目标生成树为最大生成树，则所述按照权值的预设顺序为按照权值由大到小，所述预设值为最大值。7.根据权利要求7所述的方法，其特征在于，所述待压缩的图为无向图。8.一种针对目标生成树查询的图数据压缩装置，其特征在于，包括：输入模块，用于输入待压缩的图，所述图中包含结点、边和目标生成树查询所依赖的边的权值；初始化模块，用于初始化生成树覆盖子图，初始化的生成树覆盖子图只包含所述待压缩的图中的结点、不包含所述待压缩的图中的边，并在所述生成树覆盖子图上建立并查集，所述并查集存储所述生成树覆盖子图内的连通块信息；排序模块，用于将所述待压缩的图中所有的边，按照权值的预设顺序进行排序，存入一个队列中；遍历模块，用于遍历所述队列中所有权值为预设值的边，对于所述队列中所有权值为预设值的边中的任一边，判断所述边的端点是否在所述并查集中的同一连通块中，若是则2CN109885733A权利要求书2/2页将所述边标记为树外边；加入模块，用于将所述队列中已经遍历过的边移出所述队列，加入所述生成树覆盖子图，并维护加入边之后的生成树覆盖子图上的并查集；删除模块，用于判断所述队列是否为空，若是，则将所述待压缩的图中所有标记为树外边的边删除，输出删除树外边后压缩完毕的图。9.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述程序时实现如权利要求1至7任一项所述方法的步骤。10.一种非暂态计算机可