python - 在 python 中实现 DAG

Question

我正在 python 中实现一个 DAG。我正在使用字典来实现 DAG。每个键代表图中的一个节点。与键相关联的值表示依赖于该键节点的一组节点。

是否有必要使用orderedDict 而不是Dict 来实现DAG。 OrderedDict 保留了键的插入顺序。我想知道为什么当每个键的值代表一组依赖于该对应键的节点的节点时，为什么要保留 DAG 中节点的插入顺序？

Answer 1

假设您有以下 DAG:

您可以将此 DAG 表示为字典:

graph = {
    'root': ['a'],
    'a': ['b', 'e'],
    'b': ['c', 'd'],
    'd': ['e']}

您也可以将此 DAG 表示为有序字典，但这是不必要的。键/值对的顺序无关紧要。有一个错误/不完整的 Python DAG 库 that uses ordered dictionaries ，但该库不是一个很好的例子。
networkx是 Python DAG(和其他图形)的黄金标准。您可以使用表示图边的元组列表创建 networkx 有向图:

import networkx as nx

graph = nx.DiGraph()
graph.add_edges_from([("root", "a"), ("a", "b"), ("a", "e"), ("b", "c"), ("b", "d"), ("d", "e")])

见 here有关 Python DAG 的更多信息。