图遍历确保首先访问 parents

Question

我正在尝试创建一个工作流管理，我在其中用图表表示工作流。该图是一个简单的有向图，其中节点代表一些任务，边指向依赖于具有 parent->child 关系的任务的任务。现在，我想要实现的是，在所有 parent 完成之前，任何任务都不应该开始。

假设我有以下图表表示为 python 字典：

graph = {'A': ['B', 'D'], 'B': ['D', 'C'], 'C': ['D', 'E'],
     'D': ['E'], 'E': []}

在这种情况下，A 应该首先执行，然后是 B，然后是 C。之后 D 被执行，最后任务 E 完成，这取决于 D.

我可以设想这样做的一种方法是使用广度或深度优先搜索来访问所有节点，然后在每个节点检查是否所有 parent 都已完成。如果是，我将开始该任务并一直这样做，直到所有任务都已开始。

我想知道是否有更多的sophisticated/efficient解决这个问题而不是多次遍历图形？

Answer 1

您不需要多次遍历。只需一个普通的 BFS 就可以完成这项工作。在 BFS 中，parent 总是在 children 之前访问。

Answer 2

这取决于你的图形数据结构。

如果您的图形存储为节点，则可以使用 BFS，因为您将从根（最大任务依赖性）导航到叶子（最小任务依赖性），方法是从兄弟姐妹到兄弟姐妹（具有相同依赖级别的任务） ).

如果您的图表如您所解释的那样存储为邻接表，则您应该进行拓扑排序，以逐步从最大任务依赖性到最小任务依赖性。

这将为您提供然后 O(n) 遍历图的复杂度。

Answer 3

您可以使用像 graph_tool 这样的库，它实现了 topological sort：

graph = {'A': ['B', 'D'], 'B': ['D', 'C'], 'C': ['D', 'E'], 'D': ['E'], 'E': []}
i2a = dict(enumerate(graph))
a2i = {v:k for k,v in i2a.items()}

import graph_tool.all as gt
g = gt.Graph()
g.add_edge_list([(a2i[s], a2i[t]) for s in graph for t in graph[s]])
print(*[i2a[v] for v in gt.topological_sort(g)])

输出：

A B C D E

图遍历确保首先访问 parents

Graph traversal ensuring the parents are visited first

algorithm

graph

graph-algorithm