有向图的强连通分量.doc

《有向图的强连通分量.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告课程名称数据结构实验项目名称有向图的强连通分量班级与班级代码14计算机实验班实验室名称（或课室）实验楼803专业计算机科学与技术任课教师学号：姓名：实验日期：2015年12月03日广东财经大学教务处制姓名实验报告成绩评语：指导教师（签名）年月日说明：指导教师评分后，实验报告交院（系）办公室保存。一、实验目的与要求采用邻接表存储的有向图。二、实验内容（1）创建N个节点的空图DiGraphCreateGraph(intNumVertex)//创建一个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上执行DFS，通过对DFS生成森林的后序遍历对G的顶点编号。//后序DFS遍历图G，并将节点按后序遍历的顺序编号int*PostDFS(DiGraphG){intNumVertex=G->NumVertex;intvisited[NumVertex];inti;for(i=0;i

4、)FatalError("Outofspace!!!");intpostCounter=0;//定义一个内嵌的DFS函数voidDFS(Vertexv)//从节点v出发执行DFS{visited[v]=1;//标记该节点被访问PositionP=Header(G->Table[v].Header);if(!IsEmpty(G->Table[v].Header)){do//对节点v的所有邻接点递归调用DFS{P=Advance(P);Vertexw=Retrieve(P);if(visited[w]==0)//v的邻接点w未被访问过

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

6、存入post数组int*post=PostDFS(G);//求图G的逆置GRDiGraphGR=ReverseGraph(G);//按post编号从大到小顺序在GR上执行DFS，所得连通分量就是原图G的强连通分量intNumVertex=GR->NumVertex;intvisited[NumVertex];inti;for(i=0;i

7、组if(sccID==NULL)FatalError("Outofspace!!!");intsccCounter=0;//定义一个内嵌的DFS函数voidDFS(Vertexv)//从节点v出发执行DFS{visited[v]=1;//标记该节点被访问sccID[v]=sccCounter;PositionP=Header(GR->Table[v].Header);if(!IsEmpty(GR->Table[v].Header)){do//对节点v的所有邻接点递归调用DFS{P=Advance(P);Vertexw=Retrie

8、ve(P);if(visited[w]==0)//v的邻接点w未被访问过{DFS(w);}}while(!IsLast(P,GR->Table[v].Header));}}intm;for(m=NumVertex-1;m>=0;m--)//按pos