求一无向图G中所有环

1. 判断N结点的无向图G是否有环

假定：结点个数为M，边条数为E

遍历一遍，判断图分为几部分（假定为P部分，即图有 P 个连通分量）

对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1

只要有一个满足 边数 > 结点数－1
原图就有环
将P个连通分量的不等式相加，就得到：
所有边数 > 所有结点数＋连通分量个数
即： E+P>M 所以只有判断 E +P>M就表示原图有环，否则无环.

2.对于每一个连通分量,单独计算其环的个数_,则无向图G的总环数即为各连通分量环数总和

前提：对一连通分量P，将其用邻接矩阵表示法来表示

1. 用广度优先算法求出P的支撑树（即生成树），在求支撑树的过程中，用 -1表示被加入支撑树中的边。（对于无权图可以用1表示）;

2. 在邻接矩阵中寻找权值不是-1的边（当然也不是0，如果是无权图，就应该找值为1的边），假定该边连接的是节点i和j。将其边的权值改为－1;

3. 采用深度优先遍历算法求出从顶点i到顶点j之间所有简单路径（注意给每个顶点赋不同权值。例如－1，0，1分别表示未遍历，已经遍历但还有相邻结点未遍历完，已经遍历而且相邻结点已遍历完。这样做主要是为了防止回溯到上一已访问过的结点。）;

3. 根据生成树的定义，在生成树上每增加一条边，就会有一个回路。在生成树上寻找i和j的路径。将该简单路径与边（i,j）连接即得环。输出该环;

4. 继续在邻接矩阵中寻找权值不是-1的边，假定该边连接的两顶点是v和w。将其边的权值改为－1;

5. 求出从顶点i到顶点j之间的所有简单路径；

6．分别将所求出的简单路径与边（i,j）连接即得环，输出该环；

7．重复执行步骤4－7，直到在邻接矩阵中没有权值是-1的边为止。