3

数据：一个依赖列表，已经验证为非循环的。所以在这里，'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。

4

2 回答 2

6

两个答案都给出了相同的结果，但是如果我对问题的阅读是正确的，那么对给定图表的简单更改给出错误的答案 - 如果您从 '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
于 2008-09-20T17:43:51.217 回答
4

试试这个：

#!/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

给我

史蒂夫@rei:~/code/tmp
$ python recur.py
一种
C
d
e
G
F
b
于 2008-09-20T16:18:00.657 回答