确定无向图是一棵树的最佳算法

Question

5

如何确定一个无向图是一棵树的最佳算法的时间复杂度是什么？

我们可以说它是O(n)，其中n是顶点数吗？

- rakesh

2个回答

2

是的，它是O(n)的。

选择一个起始节点，并执行深度优先遍历。如果你访问了某个节点超过一次，那么它就不是一棵树。

- Anthony Blake

谢谢 Anthony…我们能用 BFS 和 O(n) 的时间做到吗？ - rakesh

3

是的，但深度优先更好，因为它能更快地找到环。 - Anthony Blake

还要验证是否访问了所有的节点，否则该图可能是一片森林。 - dieram3

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Navneet · Accepted Answer

是的，这是O（n）的。在有向图中进行深度优先搜索时，有3种非树边——横叉边、返祖边和前向边。

对于无向情况，唯一的非树边是返祖边。因此，您只需要搜索返祖边。

简而言之，选择一个起始顶点。遍历并不断检查遇到的边是否为返祖边。如果找到n-1个树边而没有找到返祖边，然后用完所有的边，就可以了。

（仅为澄清-返祖边是指其另一端的顶点已经被遇到-由于无向图的属性，另一端的顶点将成为正在构建的树中当前节点的祖先。）