我正在使用networkx构建一个DAG,表示我的几个模块之间的依赖关系。
考虑服装“模块”之间的依赖关系:

import networkx as nx
dependencies = {
    'underpants': [],
    'socks': [],
    'pants': ['underpants'],
    'shirt': [],
    'sweater': ['shirt'],
    'coat': ['shirt', 'sweater'],
    'shoes': ['socks', 'pants']
}
modules = dependencies.keys()

G = nx.DiGraph()

for mod in modules:
    G.add_node(mod)

for mod, deps in dependencies.items():
    for dep in deps:
        G.add_edge(mod, dep)

nx.draw_networkx(G)

python - 如何解决模块依赖关系的DAG?-LMLPHP
这意味着如果我想穿上鞋子,我需要穿上袜子,也要穿上裤子也就是内裤(裤子的附属物)。
我现在想要一个函数,它接受一个“module”,并以正确的顺序返回之前必须运行的所有其他模块。
示例:
prerequisites("pants") == ["underpants"]
prerequisites("underpants") == []
prerequisites("shoes") == ["underpants", "pants", "socks"]  # or: ["socks", "underpants", "pants"] would also work.

我确信这个问题存在,我只是不知道它的算法/函数名,对吧?
我认为通过list(nx.topological_sort(G))得到的拓扑顺序,几乎就是我想要的。但是在这种情况下它会返回
['shirt', 'sweater', 'coat', 'socks', 'underpants', 'pants', 'shoes']

所以如果我想穿袜子,这个结果会告诉我先穿衬衫、毛衣和外套(尽管它们是可选的,但没有依赖关系)。

最佳答案

查看深度优先搜索算法

关于python - 如何解决模块依赖关系的DAG?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/53154360/

10-09 18:18