确定无向图是否为树的最佳算法的时间复杂度是多少？
我们可以说有n个顶点的Big-oh(n)吗？
最佳答案
是的，它是O(n)。在有向图中进行深度优先搜索时，具有3种类型的非树边缘-交叉，向后和向前。
对于无方向情况，唯一的非树边缘是后边缘。因此，您只需要搜索后边缘。
简而言之，选择一个起始顶点。遍历并继续检查遇到的边缘是否为后边缘。如果找到n-1个树的边缘却没有找到后边缘，然后用尽边缘，那就太贵了。
(请澄清一下-back edge是已经遇到另一端顶点的一个-并且由于无向图的特性，另一端的顶点将是正在被树中的当前节点的祖先 build 。)
关于graph-algorithm - 确定无向图是否为树的最佳算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8367485/