Topologiese aard, rekursiewe, met behulp van kragopwekkers

Question

Data: 'n afhanklikheid lys, reeds geverifieer te asikliese wees. So hier, 'n "hang af van 'b', 'c' (c hang af van d), ens ...

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

Ek wil graag 'n top-down het, rekursiewe oplossing vir kom ons sê, vind die ketting begin by 'N': a, c, d, e, g, f, b

So, nou ( 'n nie-kragopwekker oplossing):

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

Dit is duidelik dat hierdie is redelik swak :) Ek het al gebons my kop oor hoe om hoe om opbrengste te kry binne is daar, en Ek sal enige py-cat y'all kan bring aan hierdie waardeer.

Answer 1

Probeer hierdie:

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

Gee my

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

Answer 2

Beide antwoorde gee dieselfde resultaat, maar as my lesing van die vraag korrek is gee die verkeerde antwoord op 'n eenvoudige verandering aan die gegewe grafiek - as jy 'n afhanklikheid voeg op 'c' uit 'b' (wat nie stel 'n siklus as die grafiek is gerig) die produksie is: a c d e g f b d e g f

Dit is nie heeltemal nuttig. Probeer hierdie klein variasie, wat op hoogte van wat nodes van die grafiek is reeds besoek hou:

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