邻接表 有向图 是否有环C实现 （dfs - 反向边）

与邻接矩阵 方法 类似 

利用某个节点的三种状态 判断是否有反向边  有 ？ 有环：无环

#define gray -1 #define white 0 #define black 1 bool is_dag = true;//初始为有向无环图

图的顶点与边定义： typedef struct ENode { int ivex;//顶点 索引 struct ENode* next; }ENode; typedef struct VNode { VertexType data; // 顶点 信息 ENode* first_edge; }VNode; typedef struct Graph { VNode vex[MAXVEX]; int vex_num, edge_num; }Graph; 核心代码 ： void dfs(Graph g, int i) { ENode* p; color[i] = gray; p = g.vex[i].first_edge; while (p != NULL) { if (color[p->ivex] == white) { dfs(g, p->ivex); } else if(color[p->ivex] == gray){ is_dag = false; } p = p->next; } color[i] = black; } int has_circle(Graph g)//判断图中是否有环 { int i; ENode* p; for (i = 0; i < g.vex_num; i++) { color[i] = white; } //loop_num = 0; for (i = 0; i < g.vex_num; i++) { if (color[i] == white) { dfs(g, i); //loop_num++; (统计环数量) } } if (!is_dag) return 1; else return 0; }