确定有向图或无向图是否为树 [英] Determining whether or not a directed or undirected graph is a tree
问题描述
我想知道一种快速算法来确定有向图或无向图是树.
或深度优先搜索来自该顶点.如果你遇到一个已经访问过的顶点，它不是一棵树.
如果您已完成并且有未探索的顶点，则它不是树 - 图未连接.
否则，它就是一棵树.
要检查二叉树，还要检查每个顶点是否最多有 2 个输出边.
对于无向图:
使用简单的深度优先搜索(从任何顶点开始)检查循环 - 如果一条未探索的边导致一个之前访问过的节点，那么该图包含一个循环."如果有一个循环，它不是一棵树.
如果上述过程留下一些未探索的顶点，则它不是树，因为它没有连接.
否则，它就是一棵树.
要检查二叉树，如果图有多个顶点，还要检查所有顶点是否有 1-3 条边(1 条到父级，2 条到子级).
没有必要检查根，即一个顶点是否包含 1-2 条边，因为必须在无环连通无向图中存在具有 1-2 条边的顶点.
请注意，识别根通常是不可能的(在特殊情况下可能是可能的)，因为在许多无向图中，如果我们将其设为二叉树，则可以将多个节点设为根.
I would like to know of a fast algorithm to determine if a directed or undirected graph is a tree.
This post seems to deal with it, but it is not very clear; according to this link, if the graph is acyclic, then it is a tree. But if you consider the directed and undirected graphs below: in my opinion, only graphs 1 and 4 are trees. I suppose 3 is neither cyclic, nor a tree.
What needs to be checked to see if a directed or undirected graph is a tree or not, in an efficient way? And taking it one step ahead: if a tree exists then is it a binary tree or not?
For a directed graph:
Find the vertex with no incoming edges (if there is more than one or no such vertex, fail).
Do a breadth-first or depth-first search from that vertex. If you encounter an already visited vertex, it's not a tree.
If you're done and there are unexplored vertices, it's not a tree - the graph is not connected.
Otherwise, it's a tree.
To check for a binary tree, additionally check if each vertex has at most 2 outgoing edges.
For an undirected graph:
Check for a cycle with a simple depth-first search (starting from any vertex) - "If an unexplored edge leads to a node visited before, then the graph contains a cycle." If there's a cycle, it's not a tree.
If the above process leaves some vertices unexplored, it's not a tree, because it's not connected.
Otherwise, it's a tree.
To check for a binary tree, if the graph has more than one vertex, additionally check that all vertices have 1-3 edges (1 to the parent and 2 to the children).
Checking for the root, i.e. whether one vertex contains 1-2 edges, is not necessary as there has to be vertices with 1-2 edges in an acyclic connected undirected graph.
Note that identifying the root is not generically possible (it may be possible in special cases) as, in many undirected graphs, more than one of the nodes can be made the root if we were to make it a binary tree.
这篇关于确定有向图或无向图是否为树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
