判断一个图是否有环无向图有向图讲解.doc

一、无向图：方法1：如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。n算法：第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。如果最后还有未删除顶点，则存在环，否则没有环。n算法分析：由于有m条边，n个顶点。i)如果m>=n，则根据图论知识可直接判断存在环路。（证明：如果没有环路，则该图必然是k棵树k>=1。根据树的性质，边的数目m=n-k。k>=1，所以：m<n）ii)如果m<n则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。这两种操作的总数不会超过m+n。由于m<n，所以算法复杂度为O(n)。注：该方法，算法复杂度不止O(V)，首先初始时刻统计所有顶点的度的时候，复杂度为(V+E)，即使在后来的循环中E>=V，这样算法的复杂度也只能为O(V+E)。其次，在每次循环时，删除度为1的顶点，那么就必须将与这个顶点相连的点的度减一，并且执行deletenodefromlist[list[node]]，这里查找的复杂度为list[list[node]]的长度，只有这样才能保证当degree[i]=1时，list[i]里面只有一个点。这样最差的复杂度就为O(EV)了。方法2：DFS搜索图，图中的边只可能是树边或反向边，一旦发现反向边，则表明存在环。该算法的复杂度为O(V)。方法3：摘自：HYPERLINK"http://blog.csdn.net/lzrzhao/archive/2008/03/13/2175787.aspx"http://blog.csdn.net/lzrzhao/archive/2008/03/13/2175787.aspxPS：此方法于2011-6-12补充假定：图顶点个数为M，边条数为E遍历一遍，判断图分为几部分（假定为P部分，即图有P个连通分量）对于每一个连通分量，如果无环则只能是树，即：边数＝结点数－1只要有一个满足边数>结点数－1原图就有环将P个连通分量的不等式相加，就得到：P1:E1=M1-1P2:E2=M2-1...PN:EN>MN-1所有边数(E)>所有结点数(M)-连通分量个数(P)即：E+P>M所以只要判断结果E+P>M就表示原图有环，否则无环.实例代码如下：#include<iostream>#include<malloc.h>usingnamespacestd;#definemaxNum100//定义邻接举证的最大定点数intvisited[maxNum];//通过visited数组来标记这个顶点是否被访问过，0表示未被访问，1表示被访问intDFS_Count;//连通部件个数，用于测试无向图是否连通，DFS_Count=1表示只有一个连通部件，所以整个无向图是连通的intpre[maxNum];intpost[maxNum];intpoint;//pre和post的值//图的邻接矩阵表示结构typedefstruct{charv[maxNum];//图的顶点信息inte[maxNum][maxNum];//图的顶点信息intvNum;//顶点个数inteNum;//边的个数}graph;voidcreateGraph(graph*g);//创建图gvoidDFS(graph*g);//深度优先遍历图gvoiddfs(graph*g,inti);//从顶点i开始深度优先遍历与其相邻的点voiddfs(graph*g,inti){//cout<<"顶点"<<g->v[i]<<"已经被访问"<<endl;cout<<"顶点"<<i<<"已经被访问"<<endl;visited[i]=1;//标记顶点i被访问pre[i]=++point;for(intj=1;j<=g->vNum;j++){if(g->e[i][j]!=0&&visited[j]==0)dfs(g,j);}post[i]=++point;}voidDFS(graph*g){inti;//初始化visited数组，表示一开始所有顶点都未被访问过for(i=1;i<=g->vNum;i++){visited[i]=0;pre[i]=0;post[i]=0;}//初始化pre和postpoint=0;//初始化连通部件数为0DFS_Count=0;//深度优先搜索for(i=1;i<=g->vNum;i++){if(visited[i]==0)//如果这个顶点为被访问过，则从i顶点出发进行深度优先遍历{DFS_Count++;//统计调用voiddfs(graph*g,inti);的次数dfs(g,i);}}}voidcre