الطوبوغرافية نوعا ما, العودية, باستخدام مولدات

Question

البيانات:تبعية قائمة بالفعل التحقق من أن تكون حلقية.حتى هنا, 'a' يعتمد على 'b','c' (c يعتمد على د) ، الخ...

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

أود أن يكون من أعلى إلى أسفل ، العودية حل دعونا نقول العثور على سلسلة ابتداء من الساعة 'أ':a ، c ، d ، e ، g ، f ، ب

حتى الآن (غير مولد الحل):

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-فو جميعا يمكن أن تجلب إلى هذا.

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

كل الإجابات تعطي نفس النتيجة ، ولكن إذا قراءتي السؤال الصحيح هو إعطاء إجابة خاطئة تغيير بسيط إلى بالنظر إلى الرسم البياني - إذا قمت بإضافة الاعتماد على 'ج' من 'ب' (والتي لا نقدم دورة في الرسم البياني يتم توجيه) الناتج هو: 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