∙注：
该方法，算法复杂度不止O(V)，首先初始时刻统计所有顶点的度的时候，复杂度为(V + E)，即使在后来的循环中E>=V，这样算法的复杂度也只能为O(V + E)。其次，在每次循环时，删除度为1的顶点，那么就必须将与这个顶点相连的点的度减一，并且执行delete node from list[list[node]]，这里查找的复杂度为list[list[node]]的长度，只有这样才能保证当degree[i]=1时，list[i]里面只有一个点。这样最差的复杂度就为O(EV)了。
方法2：
DFS搜索图，图中的边只可能是树边或反向边，一旦发现反向边，则表明存在环。该算法的复杂度为O(V)。
方法3：
摘自：
/lzrzhao/archive/2008/03/13/2175787.aspx PS：此方法于2011-6-12补充
假定：图顶点个数为M，边条数为E
遍历一遍，判断图分为几部分（假定为P部分，即图有P 个连通分量）
对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1
只要有一个满足边数> 结点数－1
原图就有环
将P个连通分量的不等式相加，就得到：
P1:E1=M1-1
P2:E2=M2-1
...
PN:EN>MN-1
所有边数(E) > 所有结点数(M) - 连通分量个数(P)
即： E + P > M 所以只要判断结果 E + P > M 就表示原图有环，否则无环.
实例代码如下：
1.#include
2.#include
ing namespace std;
4.#define maxNum 100 //定义邻接举证的最大定点数
5.int visited[maxNum];//通过visited数组来标记这个顶点是否被访问过，0表示未被访问，
1表示被访问
6.int DFS_Count;//连通部件个数，用于测试无向图是否连通，DFS_Count=1表示只有一个连通
部件，所以整个无向图是连通的
7.int pre[maxNum];
8.int post[maxNum];
9.int point;//pre和post的值
10.
11.//图的邻接矩阵表示结构
12.typedef struct
13.{
14.char v[maxNum];//图的顶点信息
15.int e[maxNum][maxNum];//图的顶点信息
16.int vNum;//顶点个数
17.int eNum;//边的个数
18.}graph;
19.void createGraph(graph *g);//创建图g
20.void DFS(graph *g);//深度优先遍历图g
21.void dfs(graph *g,int i);//从顶点i开始深度优先遍历与其相邻的点
22.void dfs(graph *g,int i)
23.{
24.//cout<<"顶点"<v[i]<<"已经被访问"<25. cout<<"顶点"<26. visited[i]=1;//标记顶点i被访问
27. pre[i]=++point;
28.for(int j=1;j<=g->vNum;j++)
29. {
30.if(g->e[i][j]!=0&&visited[j]==0)
31. dfs(g,j);
32. }
33. post[i]=++point;
34.}
35.
36.void DFS(graph *g)
37.{
38.int i;
39.//初始化visited数组，表示一开始所有顶点都未被访问过
40.for(i=1;i<=g->vNum;i++)
41. {
42. visited[i]=0;
43. pre[i]=0;
44. post[i]=0;
45. }
46.//初始化pre和post
47. point=0;
48.//初始化连通部件数为0
49. DFS_Count=0;
50.//深度优先搜索
51.for(i=1;i<=g->vNum;i++)
52. {
53.if(visited[i]==0)//如果这个顶点为被访问过，则从i顶点出发进行深度优先遍
历
54. {
55. DFS_Count++;//统计调用void dfs(graph *g,int i);的次数
56. dfs(g,i);
57. }
58. }
59.}
60.void createGraph(graph *g)//创建图g
61.{
62. cout<<"正在创建无向图..."<63. cout<<"请输入顶点个数vNum:";
64. cin>>g->vNum;
65. cout<<"请输入边的个数eNum:";
66. cin>>g->eNum;
67.int i,j;
68.//输入顶点信息
69.//cout<<"请输入顶点信息："<70.//for(i=0;ivNum;i++)
