有向圖的強(qiáng)連通分量.doc

《有向圖的強(qiáng)連通分量.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目名稱有向圖的強(qiáng)連通分量班級與班級代碼14計(jì)算機(jī)實(shí)驗(yàn)班實(shí)驗(yàn)室名稱（或課室）實(shí)驗(yàn)樓803專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)任課教師學(xué)號：姓名：實(shí)驗(yàn)日期：2015年12月03日廣東財(cái)經(jīng)大學(xué)教務(wù)處制姓名實(shí)驗(yàn)報(bào)告成績評語：指導(dǎo)教師（簽名）年月日說明：指導(dǎo)教師評分后，實(shí)驗(yàn)報(bào)告交院（系）辦公室保存。一、實(shí)驗(yàn)?zāi)康呐c要求采用鄰接表存儲(chǔ)的有向圖。二、實(shí)驗(yàn)內(nèi)容（1）創(chuàng)建N個(gè)節(jié)點(diǎn)的空圖DiGraphCreateGraph(intNumVertex)//創(chuàng)建一個(gè)N個(gè)節(jié)點(diǎn)的空圖{DiGraphG;G=malloc(sizeof(struct

2、Graph));if(G==NULL)FatalError("Outofspace!!!");G->Table=malloc(sizeof(structTableEntry)*NumVertex);if(G->Table==NULL)FatalError("Outofspace!!!");G->NumVertex=NumVertex;G->NumEdge=0;inti;for(i=0;iTable[i].Header=MakeEmpty(NULL);G->Table[i].V=i;}retur

3、nG;}（2）在圖G上執(zhí)行DFS，通過對DFS生成森林的后序遍歷對G的頂點(diǎn)編號。//后序DFS遍歷圖G，并將節(jié)點(diǎn)按后序遍歷的順序編號int*PostDFS(DiGraphG){intNumVertex=G->NumVertex;intvisited[NumVertex];inti;for(i=0;i

4、)FatalError("Outofspace!!!");intpostCounter=0;//定義一個(gè)內(nèi)嵌的DFS函數(shù)voidDFS(Vertexv)//從節(jié)點(diǎn)v出發(fā)執(zhí)行DFS{visited[v]=1;//標(biāo)記該節(jié)點(diǎn)被訪問PositionP=Header(G->Table[v].Header);if(!IsEmpty(G->Table[v].Header)){do//對節(jié)點(diǎn)v的所有鄰接點(diǎn)遞歸調(diào)用DFS{P=Advance(P);Vertexw=Retrieve(P);if(visited[w]==0)//v的鄰接點(diǎn)w未被訪問過

5、{DFS(w);}}while(!IsLast(P,G->Table[v].Header));}post[v]=postCounter;postCounter++;}Vertexj;for(j=0;j

6、存入post數(shù)組int*post=PostDFS(G);//求圖G的逆置GRDiGraphGR=ReverseGraph(G);//按post編號從大到小順序在GR上執(zhí)行DFS，所得連通分量就是原圖G的強(qiáng)連通分量intNumVertex=GR->NumVertex;intvisited[NumVertex];inti;for(i=0;i

7、組if(sccID==NULL)FatalError("Outofspace!!!");intsccCounter=0;//定義一個(gè)內(nèi)嵌的DFS函數(shù)voidDFS(Vertexv)//從節(jié)點(diǎn)v出發(fā)執(zhí)行DFS{visited[v]=1;//標(biāo)記該節(jié)點(diǎn)被訪問sccID[v]=sccCounter;PositionP=Header(GR->Table[v].Header);if(!IsEmpty(GR->Table[v].Header)){do//對節(jié)點(diǎn)v的所有鄰接點(diǎn)遞歸調(diào)用DFS{P=Advance(P);Vertexw=Retrie

8、ve(P);if(visited[w]==0)//v的鄰接點(diǎn)w未被訪問過{DFS(w);}}while(!IsLast(P,GR->Table[v].Header));}}intm;for(m=NumVertex-1;m>=0;m--)//按pos