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

Question

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

a -> b -> c

该图的边集是

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

因此,将有向图作为一组边,如何确定有向图是否为树？如果它是树,那么树的根节点是什么？

首先,我在看你如何表示这个图,邻接列表/邻接矩阵/其他什么？如何利用您选择的表示来有效地回答上述问题？

编辑1:

有些人正在考虑使用DFS进行循环检测,但问题是从哪个节点启动DFS.由于它是有向图,我们无法从随机节点启动DFS,例如,如果我从顶点'c'开始DFS,它将不会继续进行,因为没有后边缘去任何其他节点.这里的后续问题应该是如何确定这棵树的根源.

Answer 1

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

1. 找到未显示为任何边的目标的节点集R. 如果R没有恰好一个成员,则图形不是树.

2. 如果R确实只有一个成员r,那么它是唯一可能的根.

3. 马克河

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

5. 如果在步骤3结束时未标记任何节点,则该图形不是树.

如果这些步骤都没有发现图形不是树,则图形是以r为根的树.

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