有向图的强连通分量

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