首页/ 北京柏睿数据技术股份有限公司/ 专利详情

一种获取指定顶点拓扑序列的方法和设备

基本信息

申请号 CN202111076079.2 申请日 -
公开（公告）号 CN113901275A 公开（公告）日 2022-01-07
申请公布号 CN113901275A 申请公布日 2022-01-07
分类号 G06F16/901（2019.01）I;G06F8/30（2018.01）I 分类 计算；推算；计数;
发明人 刘睿民;李天砚;易水寒 申请（专利权）人 北京柏睿数据技术股份有限公司
代理机构 北京睿博行远知识产权代理有限公司 代理人 申超平
地址 100102北京市朝阳区利泽西街6号院3号楼7层701内5
法律状态 -

摘要

摘要 本发明公开了一种获取指定顶点拓扑序列的方法和设备，有向图中各顶点带有标记，该方法包括：当检测到对有向图中指定顶点的拓扑序列的获取指令时，基于深度优先搜索函数从指定顶点开始对指定顶点以及指定顶点上游的各父亲顶点进行逆向遍历；根据逆向遍历的结果生成拓扑序列；其中，标记在当前顶点未被访问时为第一标记，标记在当前顶点已被访问且当前顶点存在未被访问的父亲顶点时为第二标记，标记在当前顶点已被访问且当前顶点不存在未被访问的父亲顶点时为第三标记，拓扑序列中各顶点的标记为第三标记，从而避免了对整个有向图进行扫描和遍历，避免了计算资源的浪费，提高了获取有向图中指定顶点的拓扑序列的效率。