独立节点

Question

我希望找到DAG的每个节点的独立节点。做到这一点的最简单的方法是访问前任和继任者，并将其从集合中移除。但是，如果有很多节点，这种方法需要很长的时间。找到独立节点的最佳方法是什么？

独立节点：如果不能使用当前节点的前代或后继节点访问节点而不切换(使用前辈或后继节点)，则它们是独立的。(见示例)

示例：

​

​

• A：{E}
• G：{B, C}
• D：{}

Answer 1

好吧，我不认为有其他的方法，但是无论如何，即使你每次访问所有的节点，复杂度不会超过O(节点)来寻找一个节点的独立节点wrt，您也可以使用BFS来实现这种方法。