判断有向图中是否有环

  1 #include<iostream>
  2 #include<malloc.h>
  3 using namespace std;
  4 #define maxNum 110 ///定义邻接举证的最大定点数
  5 int pre[maxNum];
  6 int post[maxNum];
  7 int point=0;///pre和post的值
  8 bool is_DAG=true;///标识位，表示有向无环图
  9 /*
 10 顶点颜色表 vis[u]
 11 　　 0 白色，未被访问过的节点标白色
 12 　　 -1 灰色，已经被访问过一次的节点标灰色
 13 　　 1 黑色，当该节点的所有后代都被访问过标黑色
 14 反向边：
 15 　　 如果第一次访问(u,v)时v为灰色，则(u,v)为反向边。在对图的深度优先搜索中没有发现
 16 　　 反向边，则该图没有回路
 17 程序判断依据：
 18     仍然是按图的节点深度遍历，访问到V时，V若被访问过，那么有2种状态：
 19     vis[u]=-1，程序跳出，存在环
 20     vis[u]=1，程序继续，这不是环
 21 时间复杂度：O(n+e)
 22 */
 23 int vis[maxNum];///顶点颜色表 vis[u]
 24 ///图的邻接矩阵表示结构
 25 typedef struct
 26 {
 27     char v[maxNum];///图的顶点信息
 28     int e[maxNum][maxNum];///图的顶点信息
 29     int vNum;///顶点个数
 30     int eNum;///边的个数
 31 } graph;
 32 
 33 void dfs(graph *g,int i)///从顶点i开始深度优先遍历与其相邻的点
 34 {
 35     vis[i]=-1;
 36     pre[i]=++point;
 37     for(int j=1; j<=g->vNum; j++)
 38     {
 39         if(g->e[i][j]!=0)
 40         {
 41             if(vis[j]==-1)///探索到回边,存在环
 42             {
 43                 is_DAG=false;///不是有向无环图
 44             }
 45             else if(vis[j]==0)
 46                 dfs(g,j);
 47         }
 48     }
 49     post[i]=++point;
 50     vis[i]=1;///表示i的后裔节点都被访问过
 51 }
 52 void DFS(graph *g)
 53 {
 54     int i;
 55     ///初始化vis数组，表示一开始所有顶点都未被访问过，初始化pre和post
 56     for(i=1; i<=g->vNum; i++)
 57     {
 58         vis[i]=0;
 59         pre[i]=0;
 60         post[i]=0;
 61     }
 62     ///深度优先搜索
 63     for(i=1; i<=g->vNum; i++)
 64     {
 65         if(!vis[i])
 66         {
 67             ///如果这个顶点为被访问过，则从i顶点出发进行深度优先遍历
 68             dfs(g,i);
 69         }
 70     }
 71 }
 72 void createGraph(graph *g,int n)///创建图g
 73 {
 74     g->vNum = n;
 75     cin>>g->eNum;
 76     int i,j;
 77     ///初始画图g
 78     for(i=1; i<=g->vNum; i++)
 79         for(j=1; j<=g->vNum; j++)
 80             g->e[i][j]=0;
 81     for(int k=1; k<=g->eNum; k++)
 82     {
 83         cin>>i>>j;
 84         g->e[i][j]=1;
 85     }
 86 }
 87 int main()
 88 {
 89     int n;
 90     while(cin>>n)
 91     {
 92         graph *g;
 93         g=(graph*)malloc(sizeof(graph));
 94         createGraph(g,n);///创建图g
 95         if(n == 1)
 96         {
 97             cout<<"YES
";
 98             continue;
 99         }
100         DFS(g);///深度优先遍历
101         if(is_DAG)///是无向图
102             cout<<"YES
";
103         else
104             cout<<"NO
";
105     }
106     return 0;
107 }
以后当模板了