問題描述

看王道視頻的時候，有一道思考題，沒有找到理想的答案，所以自己思考了一下，記錄一下。
問題問的是：在采用DFS算法實現(xiàn)AOV網(wǎng)的逆拓?fù)渑判驎r如何判斷是否有回路?

思路分析

首先，要理解，在采用DFS算法（深度優(yōu)先搜索）實現(xiàn)AOV網(wǎng)的拓?fù)渑判颍浔举|(zhì)上是對AOV網(wǎng)的DFS生成森林進(jìn)行中序遍歷，也就是相當(dāng)于對生成森林中的每一棵樹進(jìn)行后根遍歷。在對森林中每一棵樹進(jìn)行后根遍歷產(chǎn)生的序列就是對AOV網(wǎng)的逆拓?fù)渑判颉?br> 例如下面這張AOV網(wǎng)：

其DFS生成森林為
對每一棵樹進(jìn)行后根遍歷，得到的序列為2，3，1，0，4，5，也就是AOV網(wǎng)的逆拓?fù)渑判颉Ｒ来芜x取圖中出度為0的頂點，再刪除鄰接到該頂點的邊（也就是箭頭指向該頂點的邊），再選取圖中出度為0的頂點，直到所有頂點都選過一遍，這樣也可以得到上面的逆拓?fù)渑判蛐蛄小?br> 所以，在對DFS生成森林中每一棵樹進(jìn)行后根遍歷產(chǎn)生的序列就是對AOV網(wǎng)的逆拓?fù)渑判颉?br> 現(xiàn)在，DFS生成森林中的邊肯定是圖中已有的邊，現(xiàn)在將圖中的其他邊表示在DFS生成森林中，如下圖所示

其實自己試一下，可以發(fā)現(xiàn)當(dāng)圖中沒有回路時，圖中其他不在DFS生成森林當(dāng)中的弧加到森林中，這些弧都是從右邊的子樹指向其左邊的子樹或者是從某結(jié)點指向其子孫結(jié)點的，可以自己試一下。這也可以解釋為什么對DFS生成森林的中序遍歷，也就是對森林中每棵樹的后根遍歷，與逆拓?fù)渑判虻乃枷胧且恢碌摹?br> 這里補充一下逆拓?fù)渑判虻乃枷氚?br> 逆拓?fù)渑判颍?br> 1.從AOV網(wǎng)中選擇一個沒有后繼(出度為0)的頂點并輸出。
2.從網(wǎng)中刪除該頂點和所有以它為終點的有向邊。
3.重復(fù)1和2直到當(dāng)前的AOV網(wǎng)為空。
出度為0的頂點也就是沒有后驅(qū)活動的或者后驅(qū)活動都已經(jīng)完成的頂點，本身AOV網(wǎng)就是用頂點表示活動。

對每棵樹的后根遍歷都是從下往上，從左往右，這樣選取的頂點的后驅(qū)活動都已經(jīng)完成了，也就是出度為0的頂點。
上面說，AOV網(wǎng)中其他的，不在DFS生成森林當(dāng)中的弧加到DFS生成森林中后，這些弧都是從右邊的子樹指向其左邊的子樹或者是從某結(jié)點指向其子孫結(jié)點的，也就是右邊的子樹的結(jié)點的后驅(qū)活動只可能在左邊的子樹里或者其子孫，那么按照對DFS生成森林中每棵樹的后根遍歷，就能保證每次遍歷的結(jié)點，它的后驅(qū)活動都已經(jīng)完成了或者它沒有后驅(qū)活動。

有些啰嗦了，下面進(jìn)入正題。
什么時候說明AOV網(wǎng)中有回路呢？
如果在DFS的生成森林中的生成樹中，出現(xiàn)一條從頂點u到頂點v的回邊，且u在生成樹上是v的子孫，則AOV網(wǎng)中必定存在包含頂點v和頂點u的環(huán)。
也就是說生成樹中（此時說的生成樹，是指AOV網(wǎng)中不在DFS生成森林當(dāng)中的弧加到了DFS生成森林中后的樹）有子孫到祖先的弧，則說明有回路。
可以用一個isPointed[]數(shù)組記錄該結(jié)點是否被其子孫指向，也就是：是否有其子孫到該結(jié)點的弧。
每訪問一個結(jié)點時，將其指向的結(jié)點的isPointed[]設(shè)為true。
利用對樹的后根遍歷，每當(dāng)從其所有子孫返回時，判斷是否有子孫指向該結(jié)點,即if(isPointed[v]==true)，若有子孫指向該結(jié)點，則說明有回路。
首先將根結(jié)點作為祖先結(jié)點，看是否有子孫指向它，再將根結(jié)點的第一個孩子作為祖先結(jié)點，看是否有其子孫指向它，其實這里是樹的先根遍歷的思想，只要把visit();函數(shù)放在最前面。
將各結(jié)點當(dāng)做祖先結(jié)點，也就是isPointed[]設(shè)置為false.

代碼實現(xiàn)

下面是C語言的代碼

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//圖的存儲結(jié)構(gòu)
//鄰接矩陣表示法 
#define MaxVertexNum 5 //頂點數(shù)目的最大值
typedef struct{
	int Vertex[MaxVertexNum];//頂點 
	int Edge[MaxVertexNum][MaxVertexNum];//邊的權(quán) ，或者無權(quán)圖0/1 
	int vexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù) 
}MGraph;
//采用DFS算法實現(xiàn)逆拓?fù)渑判?/span>
//AOV網(wǎng)是有向無環(huán)圖 
//要判斷是否有環(huán)
//全局變量 
bool  visited[MaxVertexNum];//訪問標(biāo)記數(shù)組，初始都為false，全局變量
bool isPointed[MaxVertexNum];//初始都為false，用于記錄當(dāng)前結(jié)點是否被指向
bool flag=0;//用來標(biāo)記是否出現(xiàn)了回路
int count=0;//用來記錄已經(jīng)輸出的頂點個數(shù)
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進(jìn)行深度優(yōu)先遍歷 
    int i;
    for(i=0;i<G.vexnum;i++){
    	visited[i]=false;//初始化已訪問標(biāo)記數(shù)據(jù) 
    	isPointed[i]=false;
	} 
	for(i=0;i<G.vexnum;i++){
		if(!visited[i])
		DFS(G,i);
	}
	if(flag==1){
		printf("有回路，輸出逆拓?fù)渑判蚴n");
	}
	else{
	    printf("逆拓?fù)渑判驗?\n");
		for(i=0;i<G.vexnum;i++){
	    	printf("%d\n",print[i]);//打印逆逆拓?fù)渑判?
		} 
	}
}
void DFS(MGraph G,int v){//從頂點v出發(fā)，深度優(yōu)先遍歷圖G 
	if(flag==1) return;//說明有回路，逐層返回 
	visited[v]=true;//設(shè)已訪問標(biāo)志 
	isPointed[v]=false;//將結(jié)點v當(dāng)做祖先結(jié)點 
	for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){ 
	   isPointed[w]=true;//將v指向的結(jié)點w的isPointed[]都設(shè)置為ture 
	   if(!visited[w]) DFS(G,w);//w為v的尚未訪問的鄰接頂點 
    }
    if(isPointed[v]==true) flag=1;//說明出現(xiàn)了回路 
    print[count++]=v;//將該頂點加入打印數(shù)組中 
}
//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;
}

測試結(jié)果：
用下面有回路的AOV網(wǎng)測試，可以判斷有回路

將1指定3的這條邊改為3指向1，則可以得到逆拓?fù)渑判?br>
自己的一點小筆記，有錯誤的話望指出文章來源地址http://www.zghlxwxcb.cn/news/detail-661012.html

到了這里，關(guān)于采用DFS算法實現(xiàn)逆拓?fù)渑判?，并判斷是否有回路的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！