确定无向图是否为树的最佳算法 [英] Best algorithm to determine if an undirected graph is a tree

问题描述

确定无向图是否为树的最佳算法的时间复杂度是多少?

What is the time complexity of the Best algorithm to determine if an undirected graph is a tree??

我们可以说有n个顶点的Big-oh(n)吗?

can we say Big-oh(n) , with n vertices??

推荐答案

是的，它是O(n).在有向图中进行深度优先搜索时，具有3种类型的非树边缘-交叉，向后和向前.

Yes, it is O(n). With a depth-first search in a directed graph has 3 types of non-tree edges - cross, back and forward.

对于无方向情况，唯一的非树边缘是后边缘.因此，您只需要搜索后边缘.

For an undirected case, the only kind of non-tree edge is a back edge. So, you just need to search for back edges.

简而言之，选择一个起始顶点.遍历并继续检查遇到的边缘是否为后边缘.如果您找到n-1个树的边缘却没有找到后边缘，然后用尽边缘，那么您就是金子.

In short, choose a starting vertex. Traverse and keep checking if the edge encountered is a back edge. If you find n-1 tree edges without finding back-edges and then, run out of edges, you're gold.

(仅说明一下-一个back edge是已经遇到了另一端顶点的那个对象-并且由于无向图的特性，另一端的顶点将是当前节点的祖先)正在构造的树.)

(Just to clarify - a back edge is one where the vertex at the other end has already been encountered - and because of the properties of undirected graphs, the vertex at the other end would be an ancestor of the present node in the tree that is being constructed.)

这篇关于确定无向图是否为树的最佳算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！