有向无环图的先决条件

Question

每棵树都是有向无环图 (DAG)，但存在不是树的 DAG。 a) 我们如何判断给定的 DAG 是否是树？ b) 设计一种算法来测试给定的 DAG 是否是树？

Answer 1

1. 检查是否正好有n - 1条边（其中n是顶点数）。

2. 检查是否存在入度为零的顶点。

3. 运行 从该顶点开始深度优先搜索并检查所有顶点是否可以从该顶点到达。

如果至少有一个条件不成立，则它不是一棵树。否则就是一棵树。