Nik*_*nka 3 language-agnostic algorithm graph-theory graph directed-acyclic-graphs
我有以下作业问题：
DAG：设计一个线性时间算法 ( O(|E|+|V|)) 来确定 DAG 是否具有可从其他所有顶点到达的顶点，如果是，请找出一个。
现在我解决这个问题的方法如下：->首先找到拓扑排序中最后一个顶点（称为 V）。
->现在，确定从这个顶点 V 是否可以到达反向图的每个顶点。
-> 如果每个顶点都是可达的，那么顶点 V 就是所需的顶点，否则图中没有每个其他顶点可达的顶点。
这种方法是否正确？
附注。这个问题的解决方案的提示说我应该计算每个顶点的出度。但我无法理解计算出度有何帮助。
考虑一个弧(u, v) ? E。由于该图是无环的，u因此无法从 到达v。因此u不能成为问题的解决方案。由此可知，只有出度为零的顶点才能成为解。
此外，必须恰好有一个出度为零的顶点，否则问题无解。
我把剩下的留给读者作为练习。