拓扑排序
发布时间:2020-12-20 10:46:38 所属栏目:Python 来源:网络整理
导读:#Topological Sort'''1 2 3 4 51 -2 - 13 - 14 -5 - 3''''''visited = [1,2,3,4,5]ret = [1,5]'''def travel(visited,d,ele): if ele in visited: return if ele in d: for child in d[ele]: yield from travel(visited,child) yield ele visited.add(ele)de
#Topological Sort ''' 1 2 3 4 5 1 -> 2 -> 1 3 -> 1 4 -> 5 -> 3 ''' ''' visited = [1,2,3,4,5] ret = [1,5] ''' def travel(visited,d,ele): if ele in visited: return if ele in d: for child in d[ele]: yield from travel(visited,child) yield ele visited.add(ele) def f(array: list,deps: "list of tuple"): ret = [] visited = set() d = {} for v1,v2 in deps: d[v1] = [v2] for ele in array: for n in travel(visited,ele): ret.append(n) return list(reversed(ret)) result = f ( [1,5],[ (2,1),(3,4),(5,3) ] ) print(result) [5,1] (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |