1

假设我有一个基于信号流的“程序”图（例如类似于 Simulink 的东西）。即我有一个有向图，有几个起始节点和几个结束节点以及中间的许多节点（希望没有循环关系）

是否有一个好的和/或众所周知的算法（甚至可以作为 Python 库使用）来遍历该图并给我计算顺序？

示例（方向未显示，假设显而易见）：

输入 1 输入 2
   \ \
    [-] [*]-- 输出 1
   / \ /
输入 3 [+]----- 输出 2
       /
    In4

这应该导致说明/顺序：

1. tmp1 := In1 - In3
2. Out2 := tmp1 + In4
3. 输出 1 := 输入 2 * 输出 2

谢谢！

4

1 回答 1

3

您是否正在寻找拓扑排序的某种变体？

由于您知道起始节点，因此您可以从它们开始算法。当您遇到“操作”节点时，您将使用引导您到达它的节点创建计算。自然地，图表应该在某些特定于您的问题的方面保持一致。

要在 Python 中实现这一点，您需要一个好的图形库（例如NetworkX）。拓扑排序实现起来非常简单，许多图形库已经将其作为实现算法。例如，对于 NetworkX - networkx.algorithms.dag.topological_sort。但是，如上所述，它可能不完全是拓扑排序，而是其变体。

于 2011-04-27T08:22:27.880 回答