(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111547799.2 (22)申请日 2021.12.16 (71)申请人 南京冰鉴信息科技有限公司 地址 210000 江苏省南京市 鼓楼区中山北 路99号11层 (72)发明人 李嘉明　高忠生　顾凌云　郭志攀　 王伟　严锟　陈波　 (74)专利代理 机构 成都顶峰专利事务所(普通 合伙) 51224 代理人 杨国瑞 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 40/00(2012.01) (54)发明名称 有向图循环路径检测方法及装置 (57)摘要 本申请提供一种有向图循环路径检测方法 及装置， 有向图循环路径检测方法包括： 基于预 设的递归剪枝算法对目标有向图进行剪枝处理， 以得到目标子图； 若自目标子图中检测到包含有 至少一个环路， 则在目标子图中查找全部的连通 子图， 并标记各个连通子图各自对应的循环路 径。 本申请能够有效降低有向图循环路径检测过 程中的计算复杂 度及数据存储需求， 能够提高在 有向图中检测循环路径的便捷性、 效率、 有效性 及可靠性， 更适用于超大规模复杂网络的循环路 径检测过程。 权利要求书2页 说明书12页 附图4页 CN 114239963 A 2022.03.25 CN 114239963 A 1.一种有向图循环路径检测方法， 其特 征在于， 包括： 基于预设的递归剪枝算法对目标有向图进行剪枝处 理， 以得到目标子图； 若自所述目标子图中检测到包含有至少一个环路， 则在所述目标子图中查找全部的连 通子图， 并标记各个所述连通子图各自对应的循环路径。 2.根据权利要求1所述的有向图循环路径检测方法， 其特征在于， 所述基于预设的递归 剪枝算法对目标有向图进行剪枝处 理， 以得到目标子图， 包括： 对所述目标有向图中的符合预设的特殊节点标记规则的节点进行标记， 并生成包含有 标记节点的点 集合， 其中， 该点 集合还存储有各个所述标记 节点各自对应的状态信息； 剪枝步骤： 根据当前的点集合中的各个所述标记节点各自对应的状态信息， 在所述目 标有向图中分别对各个所述标记 节点进行剪枝处 理； 递归步骤： 重新对所述目标有向图中的符合预设的特殊节点标记规则的节点进行标 记， 若对应的标记结果不为空， 则根据当前的标记结果生 成新的点集合， 并返回执行所述剪 枝步骤； 若所述标记结果 为空， 则将当前剪枝后的目标有向图确认为目标子图。 3.根据权利要求2所述的有向图循环路径检测方法， 其特征在于， 所述对所述目标有向 图中的符合预设的特殊节点标记规则的节点进行标记， 并生成包含有标记节点的点集合， 其中， 该点 集合还存储有各个所述标记 节点各自对应的状态信息， 包括： 在所述目标有向图中标记出度数量 为0和/或入度数量 为0的节点； 将标记节点均存储至点集合， 且该点集合中存储的各个所述标记节点各自对应的状态 信息包括： 出度数量和入度数量。 4.根据权利要求3所述的有向图循环路径检测方法， 其特征在于， 所述根据当前的点集 合中的各个所述标记节点各自对应的状态信息， 在所述目标有向图中分别对各个所述标记 节点进行剪枝处 理， 包括： 若当前的所述标记节点对应的状态信 息显示该标记节点的出度 数量为0且入度 数量不 为0， 则调取 该标记节点的入度集 合中的各个关联节点； 在各个所述关联节点的出度集合中分别删除所述标记节点， 并对应更新各个所述关联 节点的出度数量； 在所述目标有向图中删除所述标记 节点。 5.根据权利要求3所述的有向图循环路径检测方法， 其特征在于， 所述根据当前的点集 合中的各个所述标记节点各自对应的状态信息， 在所述目标有向图中分别对各个所述标记 节点进行剪枝处 理， 包括： 若当前的所述标记节点对应的状态信 息显示该标记节点的出度 数量不为0且入度 数量 为0， 则调取 该标记节点的出度集 合中的各个关联节点； 在各个所述关联节点的入度集合中分别删除所述标记节点， 并对应更新各个所述关联 节点的入度数量； 在所述目标有向图中删除所述标记 节点。 6.根据权利要求3所述的有向图循环路径检测方法， 其特征在于， 所述根据当前的点集 合中的各个所述标记节点各自对应的状态信息， 在所述目标有向图中分别对各个所述标记 节点进行剪枝处 理， 包括： 若当前的所述标记节点对应的状态信 息显示该标记节点的出度 数量为0且入度 数量为权　利　要　求　书 1/2 页 2 CN 114239963 A 20， 则直接自所述目标有向图中删除所述标记 节点。 7.根据权利要求1至6任一项所述的有向图循环路径检测方法， 其特征在于， 在所述基 于预设的递归剪枝算法对目标有向图进行剪枝处 理之前， 还 包括： 接收针对目标数据的团体识别请求， 其中， 该团体识别请求中包含有目标数据对应的 各个节点各自对应的属性信息， 其中， 所述属性信息包括唯一标识、 与其他节 点之间的关联 关系以及特 征信息之间的对应关系； 根据各个所述节点分别与其他节点之间的关联关系， 生成由各个节点构成的有向图， 其中， 每个节点均存 储有各自的属性信息； 判断所述有向图是否符合预设的剪枝规模要求， 若是， 则将该有向图标记为目标有向 图以进行剪枝处 理； 相对应的， 在所述标记各个所述连通子图各自对应的循环路径之后， 还 包括： 获取各个循环路径各自对应的团体数据， 且各个团体数据中均包含有对应的循环路径 中的各个节点的属性信息以及各个节点之间的关联关系； 将全部的团体数据均发送给所述团体识别请求的发出方， 以使该发出方基于所述团体 数据进行风险识别、 预警、 管控及推送处 理中的至少一项。 8.一种有向图循环路径检测装置， 其特 征在于， 包括： 递归剪枝模块， 用于基于预设的递归剪枝算法对目标有向图进行剪枝处理， 以得到目 标子图； 连通子图标记模块， 用于若自所述目标子 图中检测到包含有至少一个环路， 则在所述 目标子图中查找全部的连通子图， 并标记各个所述连通子图各自对应的循环路径。 9.一种电子设备， 包括存储器、 处理器及存储在存储器上并可在处理器上运行的计算 机程序， 其特征在于， 所述处理器执行所述计算机程序时实现权利要求1至7任一项所述的 有向图循环路径检测方法。 10.一种计算机可读存储介质， 其上存储有计算机程序， 其特征在于， 该计算机程序被 处理器执行时实现权利要求1至7任一项所述的有向图循环路径检测方法。权　利　要　求　书 2/2 页 3 CN 114239963 A 3