我想要一种拓扑排序算法，它每次都不会提供相同的排序，而是随机排序，每次排序对所有其他排序都同样可能。
生成所有可能的拓扑排序并随机选择一个是正确的，但是太慢了。生成所有排列和过滤无效的拓扑排序也很慢；如果树/森林足够宽，第一个会退化为第二个。
将新节点插入要检查的节点队列中的随机位置似乎会产生有偏差的结果，并将其放在最后并进行fisher-yates shuffle似乎也有偏差，因为两者都没有考虑到节点“隐藏”在每个节点下，即有多少节点依赖a或被b调度。a可以没有孩子，而b拥有树的其余部分。
如何在接近线性的时间内生成随机拓扑排序，每个有效排序的可能性相同？
编辑：在任何合理的时间内不可能以您想要的方式解决这个问题。这样做涉及解决#P-完全问题。最好的办法是使用概率方法。
这类似于卡恩的算法。
https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm
只要您从所有其他起始节点中随机选择每个起始节点，您就应该得到一个随机有效的拓扑排序，其概率与任何其他随机拓扑排序相同。
例如，如果我有一个图 {(5, 11)(7, 8)(7, 11)(3, 8)(3, 10)(8, 9)(11, 2)(11, 9)( 11, 10)} 其中 (a, b) 是从 a 到 b 的有向边，我首先确定 5、7 和 3 是起始节点。我会随机选择一个 (3)，然后删除以 3 开头的所有边，包括 (3,8) 和 (3, 10)。我会检查节点 8 和 10 现在是否是启动节点。他们不是。我的起始节点现在是 5 和 7。我会选择另一个随机起始节点 (7)，然后删除所有带有 7 的边，即 (7, 8) 和 (7, 11)。我会检查这些是否是起始节点。8是起始节点。我的起始节点现在是 5 和 8。我随机选择 8，用 8 删除边，其中包括 (8, 9)。我检查 9 是否是起始节点。我唯一的起始节点是 5。我选择 5，删除边 (5, 11)。11 现在是我唯一的起始节点。我选择 11，删除边缘 (11, 2)、(11, 9) 和 (11, 10)。2、9、现在有 10 个是起始节点。我随机选择 2 个，删除所有边缘。9 和 10 是我的起始节点。我选择 10，然后选择 9。
我的拓扑排序现在是 {3, 7, 8, 5 11, 2, 10, 9}
编辑：似乎找到有效拓扑排序的数量是#P-complete，这意味着您最好的选择是使用概率算法来确定每个元素可能的排序数量，然后根据总数调整概率所有起始节点的拓扑类型。
https://en.wikipedia.org/wiki/Sharp-P-complete
编辑：您可以通过选择该起始节点，删除从该起始节点开始的所有有向边，然后计算所有可能的下一步移动的数量，然后找到一个好的函数来对其进行建模，从而猜测从特定起始节点开始的拓扑排序的分数。例如，在我的例子中，如果我选择了 5，我接下来会有两个可能的动作，3 和 7。如果我选择了 3 或 7，我还有两个可能的动作。然后我会找出我还剩下多少可能的动作，然后概率性地选择一个。在这种情况下，这三个人的机会都是平等的，所以我只是随机选择一个。在这种情况下，我选择 3。然后我可以选择 5 或 7。如果我选择 5，我将只剩下一个可能的动作，即 7，如果我选择 7，我将剩下两个可能的动作。因此，7 有 2/3 的机会被选中，5 有 1/3 的机会。这个过程一直持续到你到达终点。这只是一种启发式方法，但它应该能让您很好地近似选择完全随机的有效拓扑排序。此外，在您给出的反例中，将每个起始节点的可能移动次数加一似乎得到了更好的近似值。