用于确定DAG是否具有可从其他每个顶点到达的顶点的线性时间算法？

Question

我有以下家庭作业问题：DAG：设计线性时间算法（O(|E|+|V|)），以确定DAG是否具有可从其他每个顶点到达的顶点，如果是，则找到一个顶点。

现在，我解决此问题的方法如下：->首先找到拓扑顺序中最后一个顶点（称为V）。

->现在，确定从该顶点V是否可到达反向图的每个顶点。

->如果每个顶点都是可到达的，则顶点V是必需的顶点，否则图中没有一个顶点可以从其他每个顶点到达。

此方法正确吗？

PS。这个问题的解决方案提示我应该计算每个顶点的出度。但是我无法理解计算学位如何帮助您。

Answer 1

考虑弧(u, v) ∈ E。由于该图是非循环的，因此无法从u到达v。因此，u不能解决问题。由此得出结论，只有度为零的顶点可以作为解。

此外，必须有一个顶点完全为零的顶点，否则问题将无法解决。

我将其余的内容留给读者练习。

Answer 2

作为提示，请考虑使用常规定义将DAG分为源节点（indegree 0），中间节点和宿节点（outdegree 0）。

如果DAG确实包含这样的节点（可从其他每个顶点访问），它将是什么类型的节点？

[绘制一个示例，其中有两个节点的度数为0，每个顶点都有一个顶点。

Answer 3

解决方案将计算所有顶点的出度，以查看是否存在一个单一的汇聚顶点（出度为0的顶点，这是证明。）>

声明：当且仅当存在一个单一顶点且出度为0时，DAG的顶点才能从其他顶点到达。

此语句可以通过两个步骤证明。

必要性证明：如果DAG包含每个其他顶点均可到达的顶点u，则它必须是唯一的宿顶点（出度为0的顶点）

• u的度数为0，否则为循环形式，与DAG矛盾。

不能存在另一个具有0向外度的宿顶点v，否则u无法从v到达]]

已证明。

充分性证明：如果DAG包含一个单一的汇聚点u，那么每个其他顶点都应可到达u。

假设DAG中存在无法到达u的顶点。让我们将DAG中的所有顶点划分为可以到达u（$ V_y $）且不能到达u（$ V_n $）的顶点集合，然后$ V_n $中的顶点不存在任何指向顶点的顶点的边$ V_y $。

引理：任何DAG必须包含至少一个汇聚点顶点。

这很容易通过矛盾证明。假设DAG中的每个顶点都具有非零的出度，因此从一个顶点开始，我们就可以继续沿每个顶点的向外边缘遍历。由于DAG包含有限数量的顶点，因此我们最终将返回到先前访问的顶点，即检测到周期，这与DAG的定义相矛盾。

考虑由$ V_n $中的顶点及其之间的边形成的图，它也必须是DAG，否则原始图不能是DAG。假设v是此子DAG中的宿顶点，因此v在$ V_n $中没有指向顶点的出站边。

如上所述，v不能指向$ V_y $中的任何顶点，否则v可以到达u。

因此，原始DAG中v的整体外度也为0，这与DAG包含单个汇点顶点的假设相矛盾。证明。