algorithm - 如何确定给定的有向图是否为树

Question

程序的输入是图中的边集。例如考虑以下简单的有向图:

a -> b -> c

这个图的边集是

{ (b, c), (a, b) }

那么给定一个有向图作为一组边，如何确定有向图是否为树？如果是树，树的根节点是什么？

首先，我正在研究如何表示这个图、邻接列表/邻接矩阵/其他任何东西？如何利用您选择的表示有效地回答上述问题？

编辑 1:

有些人提到使用 DFS 进行循环检测，但问题是从哪个节点开始 DFS。因为它是一个有向图，我们不能从一个随机节点开始 DFS，例如如果我从顶点“c”开始 DFS，它将不会继续进行，因为没有后缘可以到达任何其他节点。这里的后续问题应该是如何确定这棵树的根。

Answer 1

这是一个相当直接的方法。可以使用邻接矩阵或边列表来完成。

1. 找到未作为任何边的目的地出现的节点的集合 R。如果 R 没有一个成员，则该图不是树。

2. 如果 R 确实只有一个成员 r，则它是唯一可能的根。

3. 标记 r.

4. 从 r 开始，递归地标记所有可以通过从源到目标的边到达的节点。如果任何节点已被标记，则存在循环并且该图不是树。 (此步骤与之前发布的答案相同)。

5. 如果在第 3 步结束时没有标记任何节点，则该图不是树。

如果这些步骤都没有发现该图不是树，则该图是一棵以 r 为根的树。

如果没有关于节点和边数的一些信息，很难知道什么是有效的。