有什么方法可以在不找到所有可能顺序的情况下计算 DAG 中拓扑排序的总数？

Question

假设这是一个问题.....

如何计算拓扑排序的总数而不查找所有顺序？

Answer 1

总的来说这是 #P-complete。这个 特定的图恰好是 series–parallel, 但是，这很容易。系列图导致的数量 每个图相乘的可能性。对于特定的图 你展示了，一共有三颗钻石，每颗都有两个 有效的扩展名，所以有八种可能性。