一種獲取指定頂點拓撲序列的方法和設(shè)備

基本信息

申請?zhí)?/td> CN202111076079.2 申請日 -
公開（公告）號 CN113901275A 公開（公告）日 2022-01-07
申請公布號 CN113901275A 申請公布日 2022-01-07
分類號 G06F16/901（2019.01）I;G06F8/30（2018.01）I 分類 計算；推算；計數(shù);
發(fā)明人 劉睿民;李天硯;易水寒 申請（專利權(quán)）人 北京柏睿數(shù)據(jù)技術(shù)股份有限公司
代理機構(gòu) 北京睿博行遠知識產(chǎn)權(quán)代理有限公司 代理人 申超平
地址 100102北京市朝陽區(qū)利澤西街6號院3號樓7層701內(nèi)5
法律狀態(tài) -

摘要

摘要 本發(fā)明公開了一種獲取指定頂點拓撲序列的方法和設(shè)備，有向圖中各頂點帶有標記，該方法包括：當檢測到對有向圖中指定頂點的拓撲序列的獲取指令時，基于深度優(yōu)先搜索函數(shù)從指定頂點開始對指定頂點以及指定頂點上游的各父親頂點進行逆向遍歷；根據(jù)逆向遍歷的結(jié)果生成拓撲序列；其中，標記在當前頂點未被訪問時為第一標記，標記在當前頂點已被訪問且當前頂點存在未被訪問的父親頂點時為第二標記，標記在當前頂點已被訪問且當前頂點不存在未被訪問的父親頂點時為第三標記，拓撲序列中各頂點的標記為第三標記，從而避免了對整個有向圖進行掃描和遍歷，避免了計算資源的浪費，提高了獲取有向圖中指定頂點的拓撲序列的效率。