确定有向图还是无向图是一棵树

对于有向图：

• 查找没有输入边的顶点（如果存在多个顶点或不存在，则失败）。

• 从该顶点进行广度优先或深度优先搜索。如果遇到已经访问过的顶点，则不是树。

• 如果您完成了 *** 作，并且有未开发的顶点，则它不是一棵树-图形未连接。

• 否则，它是一棵树。

• 要检查二叉树，请另外检查每个顶点是否最多具有2个输出边。

对于无向图：

• 通过简单的深度优先搜索（从任何顶点开始）检查循环- “如果未探索的边导致之前访问过的节点，则图形包含一个循环。”如果有一个循环，那不是一棵树。

• 如果上述过程使一些顶点无法利用，则它不是树，因为它没有连接。

• 否则，它是一棵树。

• 要检查一棵二叉树，如果图形具有多个顶点，请另外检查所有顶点具有1-3个边（父边1个，子边2个）。

检查根，即，一个顶点是否包含1-2的边缘，是没有必要的，因为 必须 是顶点与无环1-2的边连接无向图。

注意，一般情况下不可能识别根（在特殊情况下可能是可能的），因为在许多无向图中，如果要使它成为二叉树，则可以将多个节点作为根。