买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网获悉哈尔滨工业大学申请的专利一种CPU高效的大规模图数据强连通分量获取方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN115481296B 。

龙图腾网通过国家知识产权局官网在2025-07-11发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202211138474.3，技术领域涉及：G06F16/901；该发明授权一种CPU高效的大规模图数据强连通分量获取方法是由王宏志;万晓珑设计研发完成，并于2022-09-19向国家知识产权局提交的专利申请。

本一种CPU高效的大规模图数据强连通分量获取方法在说明书摘要公布了：一种CPU高效的大规模图数据强连通分量获取方法，涉及大数据处理的图计算技术领域。本发明是为了解决现有强连通分量获取方法需要消耗指数级运行时间，从而导致在单位时间内强连通分量获取效率低的问题。本发明包括：步骤一、获取磁盘存储的有向图，在有向图中加入一个虚拟节点r，并利用加入虚拟节点有向图G获取内存抽样图A和G中边的集合Ei；步骤二、利用步骤一获取的A、Ei获取磁盘存储的有向图G上所有的强连通分量。本发明用于获取大规模图数据的强连通分量。

本发明授权一种CPU高效的大规模图数据强连通分量获取方法在权利要求书中公布了：1.一种CPU高效的大规模图数据强连通分量获取方法，其特征在于所述方法具体过程为： 步骤一、获取磁盘存储的有向图，在有向图中加入一个虚拟节点r，并利用加入虚拟节点有向图G获取内存抽样图A以及G中边的集合Ei； 所述内存抽样图A中包括G上的所有节点集合； 所述内存抽样图A中的每个节点u拥有两个属性值:u.H和u.L； 其中，u.H和u.L均为整数； 所述加入虚拟节点的有向图G中所有节点均与r有一条有向边相连； 步骤二、利用步骤一获取的A、Ei获取磁盘存储的有向图G上所有的强连通分量，包括以下步骤： 步骤二一、初始化内存抽样图A、G中边的集合E0、变量i＝0； 步骤二二、判断Ei是否为空，若Ei为空则直接基于A获取G上的所有强连通分量，然后结束；若Ei不为空则执行步骤二三； 步骤二三、扫描集合Ei，然后判断Ei中的所有边是否均被扫描，若Ei中的所有边均被扫描则执行步骤二四；若Ei中的所有边没有全部被扫描则执行步骤二五； 步骤二四、判断扫描Ei过程中节点之间的相对顺序是否有变化，若有变化则令i＝i+1，然后执行步骤二二；若扫描Ei过程中节点之间的相对顺序没有变化则基于A获取G上的所有强连通分量，然后结束； 步骤二五、扫描G中的任意一条边eu，v，并获取u和v在A中对应的节点s和t，判断s和t在A中是否具有可达性或s是否等于t，若具有可达性或s＝t则执行步骤二三；若没有可达性且s≠t则将s，t加入到A中，然后执行步骤二六； 其中，v和u是两个不同的节点； 步骤二六、判断A是否可以继续被增大，若A还可以继续被增大则执行步骤二三，若A不可以继续被增大则对A进行收缩；若A可以继续被增大则将A中一棵拥有节点r的生成树T保存在内存中，并将除生成树外的其余的边数据存储到磁盘Ei+1中，然后执行步骤二三，直至Ei为空或A在扫描Ei中节点之间的相对顺序不发生变化，获得G上的所有强连通分量； 所述对A进行收缩包括：第一次收缩、第二次收缩； 所述第二次收缩包括以下步骤： 1获取第一次收缩过程每个节点的深度优先搜索顺序，并利用深度优先搜索顺序获取产生的搜索树T； 2判断经过第一次收缩后的A中的所有节点是否均被访问，若节点没有全部都被访问则执行3，若其全部节点都被访问则直接输出结果即第二次收缩后的A； 3获取当前未被访问的节点中深度优先搜索顺序最大的节点u’，然后判断u’在T上是否存在祖先w尚未被访问，若存在w尚未被访问且w不等于r则令u＝w，然后执行4；若不存在w尚未被访问或w等于r则执行4； 4将u’标记位已被访问，然后从u’开始遍历A中的所有节点，获取u’在A上的所有可达节点x，将x标记为已被访问； 5将A中在T上的所有边保留，将其余A上的边移除，然后执行2直至获得第二次收缩后的A。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人哈尔滨工业大学，其通讯地址为：150001 黑龙江省哈尔滨市南岗区西大直街92号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。