求生成树的方法

破圈法

删掉 x 个回路中的边（删边是任意的）

最后得到

$$m-x=n+1$$

所以删去 m-n-1 个边

指向原始笔记的链接

避圈法

每次选取和已经选取的边不构成回路的边

选取的边的总数为 n-1

指向原始笔记的链接

上面两种计算量比较大，涉及回路的判断，故可以用 广度优先算法 避开对回路的分析：

bfs求生成树

按 bfs 搜索，搜索完标号（可以标记深度和来源），不加入已经标注的结点，最后通过来源的标记复现出这棵树（也可以边搜索边建树）

指向原始笔记的链接