1、1/21/2輸出DAG的所有拓?fù)渑判蛐蛄?.課程設(shè)計內(nèi)容與要求用字符文件提供數(shù)據(jù)建立DAG（有向無環(huán)圖）合適的存儲結(jié)構(gòu)。編寫程序，輸出所有可能的拓?fù)渑判蛐蛄?。要求輸出的拓?fù)渑判蚪Y(jié)果用頂點(diǎn)序號或字母表示。輸出結(jié)果需存于字符文件。輸出結(jié)果中應(yīng)顯示全部拓?fù)渑判蛐蛄械臄?shù)目。如果DAG存在環(huán)（即拓?fù)渑判蚴。?，輸出結(jié)果中應(yīng)顯示拓?fù)渑判蛐蛄械臄?shù)目為0。課程設(shè)計報告要求給出詳細(xì)算法描述，在結(jié)論部分應(yīng)分析算法的時間復(fù)雜度和空間復(fù)雜度，并給出分析的結(jié)果。2.程序設(shè)計報告2.1總體設(shè)計首先創(chuàng)建有向圖鄰接表，從文件中讀取鄰接表的頂點(diǎn)和邊數(shù)，然后再讀取臨接矩陣的邊，每讀取一條邊，都將其插入到鄰接矩陣中。采用遞歸調(diào)用判

2、斷該鄰接矩陣是否為有向無環(huán)圖（DAG），如果是則找出鄰接矩陣中所有的拓?fù)渑判?，并打印到屏幕上。若含有環(huán)，則不打印結(jié)果。2.2詳細(xì)數(shù)據(jù)結(jié)構(gòu)設(shè)計采用結(jié)構(gòu)體存儲鄰接表的表結(jié)點(diǎn)，該結(jié)構(gòu)包含兩個整型數(shù)據(jù)域和兩個該結(jié)構(gòu)體的指針域。其結(jié)構(gòu)如下：typedefstructnodeinti,j;/弧的端點(diǎn)下標(biāo)structnode*hlink;structnode*vlink;OLANode;采用結(jié)構(gòu)體存儲鄰接表的頭結(jié)點(diǎn)，該結(jié)構(gòu)包含一個三個整型屬于和兩個表結(jié)點(diǎn)類型的指針域，其結(jié)構(gòu)如下：typedefstructElemTpdata;/頂點(diǎn)數(shù)據(jù)（可選）InfoTpinfo;/頂點(diǎn)信息（可選）inti;/頂點(diǎn)下標(biāo)OL

3、ANode*firstin;OLANode*firstout;OLHNode;采用結(jié)構(gòu)體存儲鄰接表，該結(jié)構(gòu)包含一個頭結(jié)點(diǎn)數(shù)組，和兩個整型數(shù)據(jù)域，其結(jié)構(gòu)如下：typedefstructOLHNodehMAX_N;/頭結(jié)點(diǎn)形成數(shù)組intn,e；/n：實際頂點(diǎn)數(shù);e:邊或弧的數(shù)目/Graphkindkind;/圖類型（可選）OLGraph；采用隊列存儲入度為零的表結(jié)點(diǎn)，隊列的結(jié)構(gòu)體包含一個整型數(shù)組，三個整型數(shù)據(jù)域，其結(jié)構(gòu)如下：typedefstructElemType*elem；intn；/隊列容量intf；/隊頭指針intr；/隊尾指針SqQueue；2.2詳細(xì)算法設(shè)計該程序的核心算法是拓?fù)渑判颍?/p>

4、拓?fù)渑判虻乃惴ㄈ缦拢海?）、采用鄰接表作為有向圖的存儲結(jié)構(gòu)。（2）、用一個數(shù)組indegree0.n-1來保存各頂點(diǎn)的入度；（3）、為避免檢測入度為0的頂點(diǎn)，設(shè)置l個隊列Q存放入度為0的頂點(diǎn)。并設(shè)置另一個隊列S存放當(dāng)前已經(jīng)遍歷過的頂點(diǎn)。開始排序前，掃描indegree向量，將入度為0的頂點(diǎn)壓入隊列Q，每次輸出入度為0的頂點(diǎn)時，只需要做出隊操作即可。刪除入度為0的頂點(diǎn)以及所有以它為尾的弧，只需要將該頂點(diǎn)的所有鄰接至頂點(diǎn)的入度減1,若減到0則入隊Q。隊Q空時結(jié)束循環(huán)。（4）、當(dāng)采用遞歸調(diào)用的方法輸出所有拓?fù)渑判驎r，每遞歸一層都新建一個隊列Q保存當(dāng)前入度為0的頂點(diǎn)，在while循環(huán)中刪除入度為0的頂

5、點(diǎn)以及所有以它為尾的弧，只需要將該頂點(diǎn)的所有鄰接至頂點(diǎn)的入度減1,若減到0則入隊Q，此操作更新indegree數(shù)組。同時將遍歷過的頂點(diǎn)入隊S。更新完indegree數(shù)組，調(diào)用遞歸函數(shù)，直至遍歷所有點(diǎn)或隊列為空時結(jié)束遞歸。（5）、結(jié)束當(dāng)前拓?fù)渑判虻倪f歸時,判斷是否遍歷了所有點(diǎn),若未遍歷所有點(diǎn),說明存在環(huán),則不打印拓?fù)渑判虻慕Y(jié)果。若遍歷了所有點(diǎn)，則打印拓?fù)渑判虻慕Y(jié)果（即隊列S中的元素）。遞歸函數(shù)回溯至上一級，并刪除隊列S中的隊尾元素。判讀當(dāng)前遞歸函數(shù)內(nèi)隊列Q是否為空，若不為空則繼續(xù)while循環(huán)，調(diào)用遞歸函數(shù)進(jìn)入下一層次遞歸。若為空則繼續(xù)回溯。主要函數(shù)說明：voidinitQueue(SqQueu

6、e&q)/初始化隊列voidclearQueue(SqQueue&q)/清空隊列intempty(SqQueue&q)/判斷隊空intfull(SqQueue&q)/判斷隊滿intinQueue(SqQueue&q,ElemTypee)/隊頭入隊intdelTail(SqQueue&q)/刪除隊尾intoutQueue(SqQueue&q,ElemType&e)/隊頭出隊，返回出隊元素voidcrtGraph1(OLGraph&G)/構(gòu)建有向圖鄰接表voidcopy(intindegree,intdegree,intn)/將數(shù)組indegree復(fù)制給degreevoidfun(OLGraphG

7、,SqQueueS,intindegree,intcount,int&n)/遞歸調(diào)用函數(shù)，判斷是否為DAGintTopologicalSort_Stack(OLGraphG)/拓?fù)渑判蜃映绦?返回拓?fù)渑判虻姆N數(shù)3.程序測試報告測試用例1：(預(yù)期結(jié)果)文件輸入的數(shù)據(jù)：(8,10)/矩陣的頂點(diǎn)個數(shù)各邊數(shù)(0,1)/以下均為邊(1,2)(2,3)(4,1)(4,2)(4,5)(5,6)(6,7)(6,3)(2,6)運(yùn)行結(jié)果：運(yùn)行結(jié)果：1/21/2hdhahdhdhdhdhdA-$2MSEEEEEGEcctfb-bcA-ffbbbbbbbb-Arx.fLtjZiK-LMAx4Ha,d.現(xiàn)o0-E2DL

8、2L測試用例2：(存在環(huán)時)文件輸入：(8,10)(0,1)(1,2)(2,3)(4,1)(2,4)(4,5)(5,6)(6,7)(6,3)(2,6)圖的結(jié)構(gòu)：4.結(jié)論測試用例一分析：如圖所示，共有十四種拓?fù)渑判蚪Y(jié)果1/21/2時間復(fù)雜度分析：初始化indegree數(shù)組：n+e次循環(huán)輸出各頂點(diǎn)入讀：n次循環(huán)每次查詢?nèi)攵葹?的頂點(diǎn)并入隊：n次循環(huán)輸出所有頂點(diǎn)：e次循環(huán)時間復(fù)雜度為：T(n,e)=Q(n+e)空間復(fù)雜度分析：遞歸的深度：n空間復(fù)雜度為：S(n)=Q(n)5.源程序附錄#include#include#include#include#defineMAX_N20/最大頂點(diǎn)數(shù)#defin

9、eQueue_size20typedefintElemTp;typedefintElemType;typedefcharInfoTp;/表結(jié)點(diǎn)結(jié)構(gòu)typedefstructnode/doublew;/弧的權(quán)重（可選）/InfoTpinfo;/弧的信息（可選）inti,j;/弧的端點(diǎn)下標(biāo)structnode*hlink;structnode*vlink;OLANode;/頭結(jié)點(diǎn)結(jié)構(gòu)typedefstructElemTpdata;/頂點(diǎn)數(shù)據(jù)（可選）InfoTpinfo;/頂點(diǎn)信息（可選）inti;/頂點(diǎn)下標(biāo)OLANode*firstin;OLANode*firstout;OLHNode;/十字鏈表

10、結(jié)構(gòu)typedefstructOLHNodehMAX_N;/頭結(jié)點(diǎn)形成數(shù)組intn,e；/n：實際頂點(diǎn)數(shù);e：邊或弧的數(shù)目/Graphkindkind;/圖類型（可選）OLGraph;typedefstructElemType*elem;intn;/隊列容量1/21/21/2intf;/隊頭指針intr;/隊尾指針SqQueue;/初始化隊列voidinitQueue(SqQueue&q)q.n=Queue_size;q.r=q.f=-1;/初始化指針q.elem=(ElemType*)malloc(q.n*sizeof(ElemType);/清空隊列voidclearQueue(SqQueu

11、e&q)q.r=q.f=-1;/*r=f=-1n-1區(qū)間的任一整數(shù)均可*/判斷隊空intempty(SqQueue&q)returnq.f=q.r;/判斷隊滿intfull(SqQueue&q)return(q.r+1)%q.n=(q.f+q.n)%q.n;/隊尾入隊intinQueue(SqQueue&q,ElemTypee)if(q.r+1)%q.n=(q.f+q.n)%q.n)printf(隊滿n);exit(0);q.r=(q.r+1)%q.n;q.elemq.r=e;return1;/入隊成功返回1/刪除隊尾intdelTail(SqQueue&q)if(q.r=q.f)printf

12、(隊空n);exit(0);q.r=(q.r-1)%q.n;return1;/入隊成功返回1/隊頭出隊intoutQueue(SqQueue&q,ElemType&e)if(q.r=q.f)printf(隊空n);exit(0);q.f=(q.f+1)%q.n;e=q.elemq.f;return1;/出隊成功返回1/構(gòu)建有向圖鄰接表voidcrtGraph1(OLGraph&G)inti,j,k;FILE*f;charc=a;if(f=fopen(input.txt,r)=NULL)printf(文件打開失敗!n);exit(0);if(!f)return;fscanf(f,(%d,%d)n

13、,&G.n,&G.e);/讀入頂點(diǎn)數(shù)和弧數(shù)for(i=0;iG.n;i+)G.hi.i=i;/初始化頂點(diǎn)序號G.=c;c+;G.hi.firstin=G.hi.firstout=NULL;for(k=0;kG.e;k+)建立e個表結(jié)點(diǎn)fscanf(f,(%d,%d)n,&i,&j);/讀入弧的始點(diǎn)和終點(diǎn)序號OLANode*pr,*p,*q=newOLANode;q-i=i;q-j=j;q-hlink=q-vlink=NULL;/水平鏈表按弧頭序號升序pr=NULL;p=G.hi.firstout;while(p&p-jhlink;if(pr=NULL)q-hlink=p;G.hi

14、.firstout=q;elsepr-hlink=q;q-hlink=p;/垂直鏈表按弧尾序號升序pr=NULL;p=G.hi.firstin;while(p&p-ivlink;if(pr=NULL)q-vlink=p;G.hi.firstin=q;elsepr-vlink=q;q-vlink=p;/建立表結(jié)點(diǎn)循環(huán)結(jié)束fclose(f);/函數(shù)結(jié)束/將數(shù)組indegree復(fù)制給degreevoidcopy(intindegree,intdegree,intn)for(inti=0;in;i+)degreei=indegreei;fun(G,S,indegree,count,n);1/21/2/

15、遞歸函數(shù)voidfun(OLGraphG,SqQueueS,intindegree,intcount,int&n)inti;if(count=G.n)n+;cout第n種情況:；while(!empty(S)outQueue(S,i);coutG.t;coutendl;return;SqQueueQ;OLANode*p;initQueue(Q);for(i=0;ihlink)-degreep-j;fun(G,S,degree,count,n);deletedegree;count-;delTail(S);clearQueue(Q);拓?fù)渑判?，返回true,表示拓?fù)渑判虺晒?；返回false表示有環(huán)intTopologicalSort_Stack(OLGraphG)/首先創(chuàng)建并初始化indegree數(shù)組int*indegree=newintG.n;inti,count=0;intn=0;OLANode*p;SqQueueS;for(i=0;iG.n;i+)indegreei=0;給indegree數(shù)組賦值，并輸出各個頂點(diǎn)的入度coutendlAOV網(wǎng)絡(luò)的邊:endl;for(i=0;ihlink)indegr