DAG 中的祖先到底是什么
What exactly are ancestors in DAG
我是图论的新手，对 DAG（或一般图中）中的祖先定义感到困惑。
For example in the following DAG
1--->2--->3<---4<---5
如果我首先从 1 个顶点开始 DFS，那么覆盖的路径是 1--2--3。接下来，如果我从顶点 5 开始 DFS，
那么走过的路就是5--4。不再访问顶点 3。所以访问顺序是1 2 3 5 4.
3的祖先呢？他们也只有1,2或4,5吗？
那么 4 的祖先 Ancestor 呢？它只是 5 还是 1,2，因为它们在访问 5 之前也被访问过？
DAG中一个顶点v的ancestors是所有顶点v'[=21的集合=] != v 这样 v 可以从 v' 到达。因此，在您的示例中，3 的祖先将是 1、2、4 和 5。
当然，如果您只是查看特定的路径，情况就不一样了：所以路径 1->2->3 中 3 的祖先将只是 1 和 2 .
我是图论的新手，对 DAG（或一般图中）中的祖先定义感到困惑。
For example in the following DAG
1--->2--->3<---4<---5
如果我首先从 1 个顶点开始 DFS，那么覆盖的路径是 1--2--3。接下来，如果我从顶点 5 开始 DFS，
那么走过的路就是5--4。不再访问顶点 3。所以访问顺序是1 2 3 5 4.
3的祖先呢？他们也只有1,2或4,5吗？
那么 4 的祖先 Ancestor 呢？它只是 5 还是 1,2，因为它们在访问 5 之前也被访问过？
DAG中一个顶点v的ancestors是所有顶点v'[=21的集合=] != v 这样 v 可以从 v' 到达。因此，在您的示例中，3 的祖先将是 1、2、4 和 5。
当然，如果您只是查看特定的路径，情况就不一样了：所以路径 1->2->3 中 3 的祖先将只是 1 和 2 .