用于生成图的递归算法

Question

我有一些作为依赖项彼此完全链接的数据库对象。我想要做的是编写一个算法来检索这些信息，并将所有这些信息表示为一个图形。现在，伪代码应该可以帮我完成这项工作，然后我应该能够编写python实现。这看起来像是一个递归算法，这就是我被卡住的地方！

 Input (Obj)
 list = obj.getDependencies():
 if list is empty:
   return obj
 else
   for items in list:
     list1 = item.getDependencies()
     if list1 is empty:
       return item
     else:
       list2 = item.getDependencies()
       ......

我的大脑在这一点上爆炸了！如何重写此算法？

Answer 1

如果我理解正确的话，您只需要树的叶节点(那些没有更多依赖项的节点)。真的是这样吗？一个使用auxiliar结构使其可运行的示例：

class Struct:
    def __init__(self, **entries): 
        self.__dict__.update(entries)        

obj = Struct(
    name="1",
    get_dependencies=lambda: [
        Struct(name="11", get_dependencies=lambda: []), 
        Struct(name="12", get_dependencies=lambda: [
            Struct(name="121", get_dependencies=lambda: [])
        ])
    ])

def get_all_dependencies(obj):
    ds = obj.get_dependencies()
    if not ds:
        yield obj
    for o in ds:
        for o2 in get_all_dependencies(o):
            yield o2

print [x.name for x in get_all_dependencies(obj)]
# ['11', '121']

如果您喜欢itertools带来的紧凑代码，那么可以使用完全相同的思想来实现不同的实现：

import itertools

def flatten(it):
    return itertools.chain.from_iterable(it)

def get_all_dependencies(obj):
    ds = obj.get_dependencies()
    return ([obj] if not ds else flatten(get_all_dependencies(o) for o in ds))

print [x.name for x in get_all_dependencies(obj)]
# ['11', '121']