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

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

试试这个：

#!/usr/bin/env python

def get_all(D, k):
    yield k
    for ii in D.get(k, []):
        for jj in get_all(D, ii):
            yield jj

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

for ii in get_all(A,'a'):
    print ii

给我

steve@rei:~/code/tmp
$ python recur.py
a
c
d
e
g
f
b

Answer 2

两个答案都给出相同的结果，但如果我对问题的解读是正确的，则给出对给定图表的简单更改的错误答案 - 如果你从'b'（不是'b'添加依赖'c'引入一个循环，如图所示）输出为： 一个 C d Ë G F b d Ë 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