是的,这是O(n)的。在有向图中进行深度优先搜索时,有3种非树边——横叉边、返祖边和前向边。对于无向情况,唯一的非树边是返祖边。因此,您只需要搜索返祖边。简而言之,选择一个起始顶点。遍历并不断检查遇到的边是否为返祖边。如果找到n-1个树边而没有找到返祖边,然后用完所有的边,就可以了。(仅为澄清-返祖边是指其另一端的顶点已经被遇到-由于无向图的属性,另一端的顶点将成为正在构建的树中当前节点的祖先。)