我有一个大型(超过 100,000 个节点)有向无环图 (DAG)，我想按顺序在每个节点上运行“访问者”类型的函数，其中顺序由图中的箭头定义。即保证在节点本身之前访问节点的所有父节点。
如果两个节点不直接或间接地相互引用，那么我不关心它们的访问顺序。
执行此操作最有效的算法是什么？
最佳答案
您必须执行 topological sort在节点上，并按结果顺序访问节点。
这种算法的复杂度是O(|V|+|E|)，已经很不错了。你想遍历所有个节点，所以如果你想要一个比这更快的算法，你将不得不在不查看所有边的情况下解决它，这将是危险的，因为一个边可能会破坏整个节点完全有序。
关于algorithm - 按顺序访问 DAG 节点的最有效方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3573770/