文章/答案/技术大牛

发布

社区首页 >问答首页 >DAG中的祖先究竟是什么？

问DAG中的祖先究竟是什么？
EN

Stack Overflow用户

提问于 2020-12-05 20:33:56

回答 1查看 507关注 0票数 1

我是图论新手，与DAG(或一般图)中的祖先定义相混淆。

For example in the following DAG

1--->2--->3<---4<---5

如果我首先从一个顶点开始DFS，那么覆盖的路径是1--2-3。接下来，如果我从顶点5启动DFS，那么所涵盖的路径是5-4。顶点3不再被访问。拜访顺序是1 2 3 5 4.

3的祖先呢?他们也只有1,2或4,5吗？4的祖先是5还是1,2也是因为他们在拜访5之前也曾被拜访过？

回答已采纳

发布于 2020-12-05 20:55:43

DAG中顶点v的祖先是所有顶点v‘!= v的集合，使得v可以从v’到达。所以在你的例子中，3的祖先是1，2，4和5。

当然，如果你只看一条特定的路径，那么路径1-> 2 ->3中的3的祖先将是1和2，这是不同的。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/65161690

复制

相似问题

问DAG中的祖先究竟是什么？EN