拓扑排序,递归,使用生成器

Question

数据:依赖列表,已经验证为非循环.所以在这里,'a'取决于'b','c'(c取决于d)等等......

A = { 'a' :  dict(b=1, c=1),
    'c' : dict(d=1),
    'd' : dict(e=1,f=1,g=1),
    'h' : dict(j=1)
    }

我想要一个自上而下的递归解决方案让我们说,找到从'a'开始的链:a,c,d,e,g,f,b

所以,现在(非发电机解决方案):

def get_all(D,k):
    L = []
    def get2(D,k):
        L.append(k)
        for ii in D.get(k,[]):
            get2(D, ii)
    get2(D,k)
    return L

显然,这是非常弱的:)我一直在试着如何在那里获得收益,并且我很感激任何py-foo你们都可以带来这个.

Answer 1

两个答案都给出了相同的结果,但是如果我对问题的解读是正确的,则给出对给定图的简单改变的错误答案 - 如果你从'b'添加对'c'的依赖(这不会引入一个循环)如图所示)输出为: a c d e g f b d e g f

这不是完全有用的.尝试这个小变化,跟踪图形的哪些节点已被访问过:

def get_all(D, k, seen=None):
    if not seen:
        seen = set( )
    if k not in seen:
        seen.add(k)
        yield k
        for ii in D.get(k, []):
            for jj in get_all(D, ii, seen):
                yield jj