确定无向图是否是树的最佳算法
确定无向图是否是树的最佳算法的时间复杂度是多少？
我们可以说 Big-oh(n) ，有 n 个顶点吗？
What is the time complexity of the Best algorithm to determine if an undirected graph is a tree??
can we say Big-oh(n) , with n vertices??
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是的，它是 O(n)。通过深度优先搜索，有向图中有 3 种类型的非树边 - 交叉边、后向边和前向边。
对于无向情况，唯一一种非树边是后边。因此，您只需要搜索后边缘即可。
简而言之，选择一个起始顶点。遍历并不断检查遇到的边是否是后边。如果你找到 n-1 条树边而没有找到后边，然后用完所有边，那么你就是黄金了。
（只是为了澄清 - 后边是已经遇到另一端的顶点的边 - 并且由于无向图的属性，另一端的顶点将是正在构建的树中存在节点。）
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.
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.
(Just to clarify - a
back edgeis 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.)是的，它是 O(n)。
选取起始节点，进行深度优先遍历。如果您多次访问一个节点，那么它就不是一棵树。
Yes, it is O(n).
Pick a starting node, and perform depth first traversal. If you visit a node more than once, it isn't a tree.