论坛 › Python › 有一个topo_sort 请大家看看

hmchzb19 发表于 2014-05-29 12:23

有一个topo_sort 请大家看看

def naive_topsort(G,S=None):
    if S is None: S=set(G)
    if len(S)==1: return list(S)
    v=S.pop()
    seq=naive_topsort(G,S)
    min_i=0
    for i,u in enumerate(seq):
      if v in G: min_i=i+1
    seq.insert(min_i,v)
    return seq两个问题：
1.我不大能看得懂这个topsort.
2.请问这里的G应该用什么样的数据结构呢？如下我尝试了N和M，M可以，N 就报错，not hashable.N=[
    set(['b','f']),
    set(['c','d','f']),
    set(['d']),
    set(['e','f']),
    set(['f']),
    set(),
    ]

set(N)

M={
    'a':set('bf'),
    'b':set('cdf'),
    'c':set('d'),
    'd':set('ef'),
    'e':set('f'),
    'f':set(),
    }

q1208c 发表于 2014-05-29 13:13

不就是个起泡排序么? :mrgreen:
拿一个数去比较一个排好序的列表, 如果比某一元素大/小, 就插在这一元素前/后 .

icymirror 发表于 2014-05-29 13:48

回复 1# hmchzb19
Topsort应当是个递归方式的插入排序。
G应当是个hashtable类的数据结构。

查看完整版本: 有一个topo_sort 请大家看看