假设我们有一个由节点 A、B、C、D 和 E 组成的 DAG。
每个节点都有一个可达节点列表——例如:
A --> B, C
A --> B
D --> E
在这种情况下，我们必须访问节点 A 和 D 才能全面访问图中的所有节点。一般来说，解决这个问题的最佳算法是什么？
最佳答案
这是一个线性方法:
- 对于每个节点计数，它的入度(指向它的边数)
- 因为图是一个 DAG(无环)，我们可以将入度为 0 的所有节点作为我们的起始子集
时间复杂度(N + M)- 与图形大小成线性
关于algorithm - 到达 DAG 中所有节点的最小节点子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55115275/