邻接表有向图是否有环 C实现（dfs

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

阅读量：4217 次

发布时间：2019-05-26

本文共 854 字，大约阅读时间需要 2 分钟。

与邻接矩阵方法类似

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

#define gray -1#define white 0#define black 1bool 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;}