拓扑排序python [英] Topological sort python

问题描述

我为 DFS 非递归编写了一个解决方案，但我无法修改它以进行拓扑排序:

def dfs(graph,start):路径 = []堆栈 = [开始]而堆栈 != []:v = stack.pop()如果 v 不在路径中: path.append(v)对于 w in reversed(graph[v]):如果 w 不在路径中并且不在堆栈中:stack.append(w)返回路径

任何想法如何修改它?

使用递归版本，我可以轻松进行排序:

def dfs_rec(graph,start,path):路径 = 路径 + [开始]对于图 [start] 中的边:如果边缘不在路径中:路径 = dfs_rec(图，边，路径)打印开始返回路径

输入:

<预><代码>>>>图 = {1: [2, 3],2: [4, 5, 6],3: [4,6],4: [5,6],5: [6],6:[]}>>>dfs_rec(graph,1,[])654231[1, 2, 4, 5, 6, 3]>>>dfs(graph,1)[1, 2, 4, 5, 6, 3]>>>图 = {1: [3],3: [5,6],5: [4],4: [7],7: [],6:[]}>>>打印 dfs_rec(graph,1,[])745631[1, 3, 5, 4, 7, 6]>>>打印 dfs(graph,1)[1, 3, 5, 4, 7, 6]

所以我也需要在非递归中得到这个顺序.

非递归解决方案:

我认为这也可能是解决方案，如果我错了，请标记我.

def dfs(graph,start):路径 = []堆栈 = [开始]标签 = len(图形)结果 = {}而堆栈 != []:#this for 循环也可以通过其他方式完成对于堆栈中的元素:如果元素不在结果中:结果[元素] = 标签标签 = 标签 - 1v = stack.pop()如果 v 不在路径中: path.append(v)对于 w in reversed(graph[v]):如果 w 不在路径中并且不在堆栈中:stack.append(w)result = {v:k for k, v in result.items()}返回路径，结果

输入:

graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}打印 dfs(graph,1)

输出:

([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})1/3/5 6/4/7

解决方案

FWIW，这是我为非递归拓扑排序编写的一些代码.

from collections import defaultdict, namedtuple从 itertools 导入 islice结果 = namedtuple('结果', ['排序', '循环'])def topological_sort(dependency_pairs):'对受依赖性约束的值进行排序'num_heads = defaultdict(int) # 指向的箭头数tails = defaultdict(list) # 出去的箭头列表head = [] # 唯一的头像列表，按第一次看到的顺序排列对于h, t independency_pairs:num_heads[t] += 1如果 h 在尾部:尾巴[h].append(t)别的:尾巴[h] = [t]head.append(h)有序 = [h 表示 h 在头中，如果 h 不在 num_heads 中]对于 h 有序:对于尾部 [h] 中的 t:num_heads[t] -= 1如果不是 num_heads[t]:订购.附加(t)循环 = [n 为 n，在 num_heads.items() 中为头，如果为头]返回结果(有序，循环)如果 __name__ == '__main__':打印(拓扑排序('aa'.split()))打印(拓扑排序('ah bg cf ch di ed fb fg hd he ib'.split()) )

I coded a solution for DFS non-recursive, but i can't modify it to make a topological sort:

def dfs(graph,start):
    path = []
    stack = [start]    
    while stack != []: 
        v = stack.pop()
        if v not in path: path.append(v)
        for w in reversed(graph[v]): 
            if w not in path and not w in stack:
                stack.append(w) 
    return path

Any ideas how to modify it?

With the recursive version i can easy have the sorting:

def dfs_rec(graph,start,path):
    path = path + [start]
    for edge in graph[start]: 
        if edge not in path:
            path = dfs_rec(graph, edge,path)
    print start
    return path

Input:

>>> graph = {
        1: [2, 3],
        2: [4, 5, 6],
        3: [4,6],
        4: [5,6],
        5: [6],
        6: []
    }
>>> dfs_rec(graph,1,[])
6
5
4
2
3
1
[1, 2, 4, 5, 6, 3]
>>> dfs(graph,1)
[1, 2, 4, 5, 6, 3]
>>> graph = {
        1: [3],
        3: [5,6],
        5: [4],
        4: [7],
        7: [],
        6: []
    }
>>> print dfs_rec(graph,1,[])
7
4
5
6
3
1
[1, 3, 5, 4, 7, 6]
>>> print dfs(graph,1)
[1, 3, 5, 4, 7, 6]

so i need to get this ordering in the non-recursive also.

Non-recursive solution:

I think that this also could be the solution, mark me if i am wrong.

def dfs(graph,start):
    path = []
    stack = [start]
    label = len(graph)
    result = {}  
    while stack != []:
        #this for loop could be done in other ways also
        for element in stack:
            if element not in result:
                result[element] = label
                label = label - 1

        v = stack.pop()
        if v not in path: path.append(v)
        for w in reversed(graph[v]): 
            if w not in path and not w in stack:
                stack.append(w) 

    result = {v:k for k, v in result.items()}
    return path,result

Input:

graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}
print dfs(graph,1) 

Output:

([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})

        1
       / 
      3
     /
    5  6
   /
  4
 /
7    

解决方案

FWIW, here is some code I worked up for a non-recursive topological sort.

from collections import defaultdict, namedtuple
from itertools import islice

Results = namedtuple('Results', ['sorted', 'cyclic'])

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    heads = []                     # unique list of heads in order first seen
    for h, t in dependency_pairs:
        num_heads[t] += 1
        if h in tails:
            tails[h].append(t)
        else:
            tails[h] = [t]
            heads.append(h)

    ordered = [h for h in heads if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.items() if heads]
    return Results(ordered, cyclic)

if __name__ == '__main__':
    print( topological_sort('aa'.split()) )
    print( topological_sort('ah bg cf ch di ed fb fg hd he ib'.split()) )

这篇关于拓扑排序python的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！