数据结构 拓扑排序拓展 如何判断DAG

有向无环图 DAG(Directed Acyclic Graph)

在学习拓扑排序的时候，我们知道如果一个有向图存在合理的拓扑序，那么这个图一定是DAG；

以下是拓扑排序的伪码描叙：

伪码描叙: 	
void TopSort()	
{
	for(图中的每一个顶点V){
	 if(Indegree[V]==0){
	 	AddQ( Q,V )；
	}
}
		
while(IsEmpty( Q )){
	V = DeleteQ( Q );
	输出V,或者记录V的输出序号;cnt++;
	for(V 的每个邻接点W ){
		Indegree[W]--;
		if(Indegree[W]==0){
			AddQ( Q,W );
		}
	}
}
		

C语言实现的拓扑排序算法

	 
bool TopSort( LGraph* Graph,Vertex TopOrder[] )
{ 
	 int Indegree[NaxVertexNum];
	 	
	 VerTex V,W;
	 for(V=0;VNv;V++){
	 		
	 	Indegree[V] = 0;
	}
		
	
	Adj* p;
	for(V=0;VNv;V++){
		for(p=Graph->G[V];p;p=p->Next){
				
			Indegree[p->AdjV]++;
		}
	}
		
	Queue* Q = Create( Graph->Nv );
		
	
	 for(V=0;VNv;V++){
	 		
	 	if( Indegree[V] == 0 ){
	 			
	 		AddQ( Q,V );
		}
	}
		
	
	 int cnt = 0; //计数器:计算已排序的顶点个数
	 while(!IsEmpty( Q )){
	 		
	 	V = Delete( Q );
	 	TopOrder[cnt++] = V;
	 		
	 	for(p=Graph->G[V];p;p=p->Next){ //对V的每个邻接点W
	 			
	 		Indegree[p->AdjV]--; //入度减1；
	 		if(Indegree[p->AdjV] == 0){
	 				
	 			AddQ( Q,p->AdjV );
			}
		}
	 }
	 	
	 if(cnt != Graph->nv){
	 	return false; //说明图中有回路,返回不成功标志
	}else{
		return true;
	}
}

所以判断有向图是否是DAG的一个方法就是拓扑排序。

不难看出借助队列实现的拓扑排序本质上是BFS：区别在于原始的BFS没有规定具体的源点；拓扑排序的源点是入度为0的顶点。

既然BFS能得出是否是DAG，那么DFS能不能得出DAG呢?

我思考了下，应该是可以的：DFS某一条路径时，如果在到达终点前再次回到这条路径中的任何一个顶点，那么就不是DAG;根据这个思路我尝试写用DFS判断DAG的代码；

DFS判断DAG的伪码描叙：

bool DFS( Vertex X )	
{
	bool IsDAG = true; 先假设是DAG
	
	if(X没有邻接点，即是一条路径的终点){
		清空之前做的标记;
		return true;
	}
	
	for(对X的每个邻接点){

		if(已经确定了不是DAG,递归不用继续了){
			return false;
		}
		
		if(X的邻接点已经标记了){
			
			那么就不是无环图;
			IsDAG = false;
			break;
		}else{

            标记X;
           
		    递归调用DFS;
		    IsDAG = DFS(X的邻接点);
        }
	}
	
	return IsDAG;
}

C语言实现的DFS判断DAG的算法

bool Visited[MaxVertexNum],collected[MaxVertexNum];

//初始化
Vertex V；
for(V=0;VNv;V++){
		
	visited[V] = false;
	collected[V] = false;
}
	
bool IsDAG = true;
for(V=0;VNv;V++){ //确保有多个起点(入度为0)时,不会遗漏任何一个
		
	if(!visited[V] && IsDAG){
			
		IsDAG = DFS( Graph,V,visited,collected ); //调用DFS
	}
}

bool DFS( LGraph* Graph,Vertex X,bool visited[],bool collected[] )
{
	bool IsDAG = true;
	
	visited[X] = true;
	
	if(Graph->G[X] == NULL){
		//递归到某条路径的终点时，初始化collected；
		Vertex V;
		for(V=0;VNv;V++){
			
			collected[V] = false;
		}
		
		return true;
	}
	
	Adj* p;
	for(p=Graph->G[X];p;p=p->Next){
		
		collected[X] = true; //某条路径开始的起点，标记一下
		
		if(IsDAG == false){  //如果已经发现有环，退出递归；
			
			return false;
		}
		
		if(collected[p->AdjV] == true){

			IsDAG = false;
			break;
		}else{	
	
			IsDAG = DFS( Graph,p->AdjV,visited,collected );
		}	
	}
	
	return IsDAG;
}

可以参考下一个实际的题目：

MOOC 数据结构 08-图8 How Long Does It Take——C语言_鸿雁丨红豆灬的博客-CSDN博客DAG，拓扑排序https://blog.csdn.net/h465705089/article/details/124815880以上就是我对有向图是否存在环的一点理解；对于无向图，两种方法也适用；递归函数DFS如果存在问题，请及时留言给我，一起进步，谢谢，诸君共勉；