基环树

基环树的定义

条边个点的连通图

• 基环树是一棵”伪树“
• 如若不保证连通，它就会成为基环树森林.

基环树的形成

1. 无向图

• 在一棵基于无向图的无根树上加一条边，构成基环树
• 去掉环上的任意一条边，基环树变为一棵真正的树

1. 有向图

• 一个DAG(有向无环图)，如果能在图中加一条边能形成一个自联通的环，则形成一棵基环树.

基础问题

找环

1.无向图
    使用拓扑排序(BFS)实现。

• 计算所有点的度数，并将度为1的点入队列；
• 从队列中弹出度为1点，并将其边去掉(相邻点度数减一)，若此时相邻点度为1，则放进队列中；
• 反复执行，直到队列为空

    操作结束后统计所有度数大于1的点，即为环上的点.