给定一个图来检测它是否是一棵树或者没有在有向图和无向图中？ [英] given a graph to detect if it is a tree or not in directed and undirected graphs?
问题描述
我想知道一个快速算法来确定一个给定的图是不是一棵树。
如果有一个循环，它不是一个循环，它不是一个循环如果上面的过程留下了一些未开发的顶点，它不是一棵树，因为它没有连接。
否则，它是一棵树。
要检查二叉树，还要检查所有顶点是否有1-3 e dges（一个给父母，2给孩子）。
检查根，即一个顶点是否包含1-2个边，这是不必要的，因为必须是在非循环连接的无向图中具有1-2个边的顶点。注意，识别根不是一般可能的（这可能是可能的在特殊情况下），因为在许多无向图中，如果我们要将它构建为二叉树，那么可以使多于一个节点成为根。
I would like to know of a fast algorithm to determine if a given graph is a tree or not. This post seems to deal with it, but not very clear. According to this, if the graph is acyclic, then it is a tree. if you consider the examples of directed and undirected graph shown, in my opinion only 1 and 4 are tree, but 3 is neither cyclic nor a tree I suppose.
so my question is: what needs to be checked to see if a graph is a tree or not for both directed and undirected graph in efficient way?
taking one step ahead to see, if a tree exists then is it a binary tree or not?
For a directed graph:
Find the vertex with only outgoing edges (if there is more than one or no such vertex, fail).
Do a BFS or DFS 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, additionally check that all vertices have 1-3 edges (one 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屋！
