我想知道一种快速算法来确定有向图还是无向图是树。
This post好像有处理,但是不是很清楚;根据这个链接,如果图是非循环的,那么它就是一棵树。但是如果你考虑下面的有向图和无向图:在我看来,只有图 1 和图 4 是树。我想 3 既不是循环的,也不是树。
需要以一种有效的方式检查有向图或无向图是否是树?更进一步:如果一棵树存在,那么它是否是一棵二叉树?
最佳答案
对于有向图:
找到没有入边的顶点(如果有多个或没有这样的顶点,则失败)。
做一个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 条边的顶点。
请注意,识别根通常是不可能的(在特殊情况下可能是可能的),因为在许多无向图中,如果我们要将其设为二叉树,则可以将多个节点设为根。
关于algorithm - 确定有向图或无向图是否为树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20556802/