1、實驗報告課程名稱 數據結構 實驗項目名稱 有向圖的強連通分量 班級與班級代碼 14計算機實驗班 實驗室名稱（或課室） 實驗樓803 專 業 計算機科學與技術 任課教師 學 號： 姓 名： 實驗日期： 2015年 12 月 03 日 廣東財經大學教務處 制姓名 實驗報告成績 評語： 指導教師（簽名） 年 月 日說明：指導教師評分后，實驗報告交院（系）辦公室保存。一、實驗目的與要求采用鄰接表存儲的有向圖。二、實驗內容（1）創建N個節點的空圖DiGraph CreateGraph(int NumVertex)/創建一個N個節點的空圖DiGraph G;G = malloc( sizeof( stru

2、ct Graph ) );if( G = NULL ) FatalError( "Out of space!" );G->Table = malloc( sizeof( struct TableEntry ) * NumVertex );if( G->Table = NULL )FatalError( "Out of space!" );G->NumVertex = NumVertex;G->NumEdge = 0;int i;for (i=0;i<NumVertex;i+)G->Tablei.Header=MakeE

3、mpty(NULL);G->Tablei.V=i; return G;（2） 在圖G上執行DFS，通過對DFS生成森林的后序遍歷對G的頂點編號。/后序DFS遍歷圖G，并將節點按后序遍歷的順序編號int *PostDFS(DiGraph G)int NumVertex=G->NumVertex;int visitedNumVertex;int i;for (i=0;i<NumVertex;i+)visitedi=0;/初始化，所有節點都未被訪問過int *post = malloc( sizeof( int ) * NumVertex );/用于存放后序DFS遍歷時，節點的編號

4、if( post = NULL ) FatalError( "Out of space!" );int postCounter=0;/定義一個內嵌的DFS函數void DFS (Vertex v)/從節點v出發執行DFSvisitedv=1;/標記該節點被訪問Position P = Header( G->Tablev.Header );if( !IsEmpty( G->Tablev.Header ) ) do/對節點v的所有鄰接點遞歸調用DFS P = Advance( P ); Vertex w=Retrieve( P ); if (visitedw=0)/

5、v的鄰接點w未被訪問過 DFS(w); while( !IsLast( P, G->Tablev.Header ) ); postv=postCounter; postCounter+;Vertex j;for (j=0;j<NumVertex;j+)/從每個節點出發進行DFS，因為圖G有可能不是連通的if (visitedj=0) DFS(j);return post;(3) 求圖G的強連通分量int *StrongConnectedComponent(DiGraph G)/求圖G的強連通分量/DFS后序遍歷圖G，并將節點按后序遍歷的順序編號存入post數組int *post=P

6、ostDFS(G);/求圖G的逆置GRDiGraph GR=ReverseGraph(G);/按post編號從大到小順序在GR上執行DFS，所得連通分量就是原圖G的強連通分量int NumVertex=GR->NumVertex;int visitedNumVertex;int i;for (i=0;i<NumVertex;i+)visitedi=0;/初始化，所有節點都未被訪問過int *sccID = malloc( sizeof( int ) * NumVertex );/用于標記強連通分量的數組if( sccID = NULL ) FatalError( "Out

7、 of space!" );int sccCounter=0;/定義一個內嵌的DFS函數void DFS (Vertex v)/從節點v出發執行DFSvisitedv=1;/標記該節點被訪問sccIDv=sccCounter;Position P = Header( GR->Tablev.Header );if( !IsEmpty( GR->Tablev.Header ) ) do/對節點v的所有鄰接點遞歸調用DFS P = Advance( P ); Vertex w=Retrieve( P ); if (visitedw=0)/v的鄰接點w未被訪問過 DFS(w);

8、while( !IsLast( P, GR->Tablev.Header ) ); int m;for (m=NumVertex-1;m>=0;m-)/按post編號從大到小順序在GR上執行DFS，因為圖G有可能不是連通的Vertex n;for (n=0;n<NumVertex;n+)if (postn=m)/節點n的編號為當前最大值if (visitedn=0)DFS(n);sccCounter+;return sccID;(4) 測試函數main()DiGraph G=CreateGraph(10);/插入15條邊，參見教科書P248，圖9-74InsertEdge(G

9、,0,1);InsertEdge(G,0,3); InsertEdge(G,1,2);InsertEdge(G,1,5);InsertEdge(G,2,0);InsertEdge(G,2,3);InsertEdge(G,2,4);InsertEdge(G,3,4);InsertEdge(G,5,2);InsertEdge(G,6,5);InsertEdge(G,6,7);InsertEdge(G,7,5);InsertEdge(G,7,9);InsertEdge(G,8,7);InsertEdge(G,9,8);/插入15條邊結束printf("輸出圖.n");OutputGraph(G);printf("n輸出圖的逆置.n");DiGraph GR=ReverseGraph(G);OutputGraph(GR);printf("n輸出后序DFS編號.n");int *pp=PostDFS(G);int i;for (i=0;i<G->NumVertex;i+)printf("%d-",ppi);printf("nn輸出強連通分量編號.n");int *scc=StrongConnectedComponen