algorithm - "Best-Effort"拓扑排序

Question

我希望根据继承来组织一些项目，目的是确定哪些项目是连接最密集的父项，并且还只是看到形成的连接。

通常这将通过拓扑排序来完成，但我的图有循环。是否有类似“尽力而为”拓扑排序的东西，它可以尝试根据连接数或类似的东西来确定“最重要”的 parent ？

例如，给定下图，我希望 1 和 2 成为顶级父级。 1 没有 parent ；虽然 2 在一个循环中，但它是比它继承的更多 child 的 parent 。

Answer 1

实现类似目标的一种方法是为每个节点计算可以从中访问多少其他节点，然后根据该数字对节点进行排序。

或者，您可以反转该逻辑。对于每个节点，计算有多少节点可以访问它，然后按升序对节点进行排序。