问题描述

看王道视频的时候，有一道思考题，没有找到理想的答案，所以自己思考了一下，记录一下。
问题问的是：在采用DFS算法实现AOV网的逆拓扑排序时如何判断是否有回路?

思路分析

首先，要理解，在采用DFS算法（深度优先搜索）实现AOV网的拓扑排序，其本质上是对AOV网的DFS生成森林进行中序遍历，也就是相当于对生成森林中的每一棵树进行后根遍历。在对森林中每一棵树进行后根遍历产生的序列就是对AOV网的逆拓扑排序。
例如下面这张AOV网：

其DFS生成森林为
对每一棵树进行后根遍历，得到的序列为2，3，1，0，4，5，也就是AOV网的逆拓扑排序。依次选取图中出度为0的顶点，再删除邻接到该顶点的边（也就是箭头指向该顶点的边），再选取图中出度为0的顶点，直到所有顶点都选过一遍，这样也可以得到上面的逆拓扑排序序列。
所以，在对DFS生成森林中每一棵树进行后根遍历产生的序列就是对AOV网的逆拓扑排序。
现在，DFS生成森林中的边肯定是图中已有的边，现在将图中的其他边表示在DFS生成森林中，如下图所示

其实自己试一下，可以发现当图中没有回路时，图中其他不在DFS生成森林当中的弧加到森林中，这些弧都是从右边的子树指向其左边的子树或者是从某结点指向其子孙结点的，可以自己试一下。这也可以解释为什么对DFS生成森林的中序遍历，也就是对森林中每棵树的后根遍历，与逆拓扑排序的思想是一致的。
这里补充一下逆拓扑排序的思想吧
逆拓扑排序：
1.从AOV网中选择一个没有后继(出度为0)的顶点并输出。
2.从网中删除该顶点和所有以它为终点的有向边。
3.重复1和2直到当前的AOV网为空。
出度为0的顶点也就是没有后驱活动的或者后驱活动都已经完成的顶点，本身AOV网就是用顶点表示活动。

对每棵树的后根遍历都是从下往上，从左往右，这样选取的顶点的后驱活动都已经完成了，也就是出度为0的顶点。
上面说，AOV网中其他的，不在DFS生成森林当中的弧加到DFS生成森林中后，这些弧都是从右边的子树指向其左边的子树或者是从某结点指向其子孙结点的，也就是右边的子树的结点的后驱活动只可能在左边的子树里或者其子孙，那么按照对DFS生成森林中每棵树的后根遍历，就能保证每次遍历的结点，它的后驱活动都已经完成了或者它没有后驱活动。

有些啰嗦了，下面进入正题。
什么时候说明AOV网中有回路呢？
如果在DFS的生成森林中的生成树中，出现一条从顶点u到顶点v的回边，且u在生成树上是v的子孙，则AOV网中必定存在包含顶点v和顶点u的环。
也就是说生成树中（此时说的生成树，是指AOV网中不在DFS生成森林当中的弧加到了DFS生成森林中后的树）有子孙到祖先的弧，则说明有回路。
可以用一个isPointed[]数组记录该结点是否被其子孙指向，也就是：是否有其子孙到该结点的弧。
每访问一个结点时，将其指向的结点的isPointed[]设为true。
利用对树的后根遍历，每当从其所有子孙返回时，判断是否有子孙指向该结点,即if(isPointed[v]==true)，若有子孙指向该结点，则说明有回路。
首先将根结点作为祖先结点，看是否有子孙指向它，再将根结点的第一个孩子作为祖先结点，看是否有其子孙指向它，其实这里是树的先根遍历的思想，只要把visit();函数放在最前面。
将各结点当做祖先结点，也就是isPointed[]设置为false.

代码实现

下面是C语言的代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//图的存储结构
//邻接矩阵表示法 
#define MaxVertexNum 5 //顶点数目的最大值
typedef struct{
	int Vertex[MaxVertexNum];//顶点 
	int Edge[MaxVertexNum][MaxVertexNum];//边的权 ，或者无权图0/1 
	int vexnum,arcnum;//图的当前顶点数和弧数 
}MGraph;
//采用DFS算法实现逆拓扑排序
//AOV网是有向无环图 
//要判断是否有环
//全局变量 
bool  visited[MaxVertexNum];//访问标记数组，初始都为false，全局变量
bool isPointed[MaxVertexNum];//初始都为false，用于记录当前结点是否被指向
bool flag=0;//用来标记是否出现了回路
int count=0;//用来记录已经输出的顶点个数
int print[MaxVertexNum];//保存要输出的顶点 

int FirstNeighbor(MGraph G,int v);//返回图G中顶点V的第一个邻接点，若有则返回该邻接点的序号，否则返回-1
int NextNeighbor(MGraph G,int v,int w);//返回图G中顶点v在顶点w之后的下一个邻接点，若有则返回该邻接点序号，否则返回-1 
void DFS(MGraph G,int v);

void DFSTraverse(MGraph G){//对图G进行深度优先遍历 
    int i;
    for(i=0;i<G.vexnum;i++){
    	visited[i]=false;//初始化已访问标记数据 
    	isPointed[i]=false;
	} 
	for(i=0;i<G.vexnum;i++){
		if(!visited[i])
		DFS(G,i);
	}
	if(flag==1){
		printf("有回路，输出逆拓扑排序失败\n");
	}
	else{
	    printf("逆拓扑排序为:\n");
		for(i=0;i<G.vexnum;i++){
	    	printf("%d\n",print[i]);//打印逆逆拓扑排序 
		} 
	}
}
void DFS(MGraph G,int v){//从顶点v出发，深度优先遍历图G 
	if(flag==1) return;//说明有回路，逐层返回 
	visited[v]=true;//设已访问标志 
	isPointed[v]=false;//将结点v当做祖先结点 
	for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ 
	   isPointed[w]=true;//将v指向的结点w的isPointed[]都设置为ture 
	   if(!visited[w]) DFS(G,w);//w为v的尚未访问的邻接顶点 
    }
    if(isPointed[v]==true) flag=1;//说明出现了回路 
    print[count++]=v;//将该顶点加入打印数组中 
}
//int FirstNeighbr(MGraph G,int v);返回图G中顶点V的第一个邻接点，若有则返回该邻接点的序号，否则返回-1
int FirstNeighbor(MGraph G,int v){
	for(int i=0;i<G.vexnum;i++){
		if(G.Edge[v][i]==1) return i;
	}
	return -1;
}
//int NextNeighbor(MGraph G,int v,int w);返回图G中顶点v在顶点w之后的下一个邻接点，若有则返回该邻接点序号，否则返回-1 
int NextNeighbor(MGraph G,int v,int w){
	for(int i=w+1;i<G.vexnum;i++){
		if(G.Edge[v][i]==1) return i;
	}
	return -1;
}
int main(){
	MGraph G;
	int i,j;
	for(i=0;i<MaxVertexNum;i++){
		for(j=0;j<MaxVertexNum;j++){
		   G.Edge[i][j]=0;
		}   
	}
	G.arcnum=5;
	G.vexnum=5;
	G.Edge[0][1]=1;
	G.Edge[0][3]=1;
	G.Edge[1][3]=1;
	G.Edge[2][1]=1;
	G.Edge[3][2]=1;
	G.Edge[4][3]=1;
	G.Edge[4][2]=1;
	DFSTraverse(G); 
	return 0;
}

测试结果：
用下面有回路的AOV网测试，可以判断有回路

将1指定3的这条边改为3指向1，则可以得到逆拓扑排序

自己的一点小笔记，有错误的话望指出