algorithm - 确定有向图或无向图是否为树

Question

我想知道一种快速算法来确定有向图还是无向图是树。

This post好像有处理，但是不是很清楚；根据这个链接，如果图是非循环的，那么它就是一棵树。但是如果你考虑下面的有向图和无向图:在我看来，只有图 1 和图 4 是树。我想 3 既不是循环的，也不是树。

需要以一种有效的方式检查有向图或无向图是否是树？更进一步:如果一棵树存在，那么它是否是一棵二叉树？

Answer 1

对于有向图:

• 找到没有入边的顶点(如果有多个或没有这样的顶点，则失败)。

• 做一个breadth-first或 depth-first search从那个顶点。如果你遇到一个已经访问过的顶点，它就不是一棵树。

• 如果完成后还有未探索的顶点，则它不是树 - 图未连接。

• 否则就是一棵树。

• 要检查二叉树，还要检查每个顶点是否最多有 2 条出边。

对于无向图:

• 使用简单的深度优先搜索(从任何顶点开始)检查循环 - "If an unexplored edge leads to a node visited before, then the graph contains a cycle."如果有一个循环，它就不是一棵树。

• 如果上述过程留下一些未探索的顶点，则它不是一棵树，因为它没有连接。

• 否则就是一棵树。

• 要检查二叉树，如果图有多个顶点，还要检查所有顶点是否有 1-3 条边(1 条到父节点，2 条到子节点)。

  检查根，即一个顶点是否包含 1-2 条边，不是必需的，因为在非循环连接的无向图中必须有具有 1-2 条边的顶点。

  请注意，识别根通常是不可能的(在特殊情况下可能是可能的)，因为在许多无向图中，如果我们要将其设为二叉树，则可以将多个节点设为根。