确定无向图是否为树的最佳算法

Question

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

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

Answer 1

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

对于无向的情况,唯一的非树边缘是后边缘.所以,你只需要搜索后边缘.

简而言之,选择一个起始顶点.遍历并继续检查遇到的边是否是后边缘.如果你发现n-1树的边缘没有找到后边缘,然后用完边缘,那你就是黄金.

(只是为了澄清 - 一个back edge是已经遇到另一端的顶点的一个 - 并且由于无向图的属性,另一端的顶点将是正在构造的树中的当前节点的祖先.)

Answer 2

是的，它是 O(n)。

选取一个起始节点，进行深度优先遍历。如果您多次访问一个节点，那么它就不是一棵树。