拓扑排序

武汉工程大学计算机科学与工程学院《数据结构》实验报告专业班级实验地点学生学号指导教师学生姓名实验时间实验项目实验类别操作性（）验证性（）设计性（）综合性（Y）其它（）实验目的及要求（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握AOV网和拓扑排序算法；（4）掌握AOE网和关键路径。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明：评阅教师：日期：年月日计算机科学与工程学院数据结构上机实验2图的应用实验目的：（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握AOV网和拓扑排序算法；（4）掌握AOE网和关键路径。2、实验内容：拓扑排序。任意给定一个有向图，设计一个算法，对它进行拓扑排序。拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。1.实验分析：主要思想：1.栈S初始化；累加器count初始化；2.扫描顶点表，将没有前驱（即入度为0）的顶点压栈；3.当栈S非空时循环3.1vj=退出栈顶元素；输出vj；累加器加1；3.2将顶点vj的各个邻接点的入度减1；3.3将新的入度为0的顶点入栈；4.if(countvertexNum)输出有回路信息该实验主要难点是解决拓扑排序的算法，先分析如下TopologicalSort(ALGraphG)//拓扑排序算法{//有向图采用邻接表存储结构//若G无回路，则flag=0,输出G的顶点的一个拓扑序列,否则给出该有向图有回路的提示.inti,count,k;int*indegree=(int*)malloc((G.vexnum+1)*sizeof(int));SqStackS;ArcNode*p;FindInDegree(G,indegree);//对顶点求入度indegree[G.vexnum]initialStack(&S);//为避免重复检测入度为0的顶点，可另设一栈暂存放所有入度为0的顶点for(i=1;i=G.vexnum;i++)if(!indegree[i])Push(&S,i);//0入度点进栈count=0;//对输出顶点计数，作为判断是否有回路的根据while(!StackEmpty(&S)){Pop(&S,&i);printf(%d,i);//输出i号顶点并计数计算机科学与工程学院数据结构上机实验3count++;for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;//表结点的数据域，即对i号顶点的每个邻接点的入度减1if(!(--indegree[k]))//若入度减少为0，则入栈Push(&S,k);}}if(countG.vexnum)//该有向图有回路return0;elsereturn1;}2.源程序代码：#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAX20typedefintVertexType;typedefstructArcNode//表结点{intadjvex;//弧所指向的顶点的位置structArcNode*nextarc;}ArcNode;typedefstructVNode//头结点{VertexTypedata;//顶点信息ArcNode*firstarc;//指向第一条依附该弧的顶点指针}VNode,*AdjList;typedefstruct{AdjListvertices;intvexnum;//图的**当前**顶点数}ALGraph;typedefstruct//栈的定义{int*base;int*top;intstacksize;}SqStack;voidinitialStack(SqStack*s)计算机科学与工程学院数据结构上机实验4{s-base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!s-base)exit(0);s-top=s-base;s-stacksize=STACK_INIT_SIZE;}voidPush(SqStack*s,inte){if(s-top-s-base=s-stacksize){s-base=(int*)realloc(s-base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(int));if(!s-base)exit(0);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;}*(s-top)++=e;}voidPop(SqStack*s,int*e){if(s-top==s-base)exit(0);*e=*--(s-top);}voidGetTop(SqStack*s,int*e){if(s-top==s-base)exit(0);*e=*(s-top-1);}intStackEmpty(SqStack*s){if(s-base==s-top)return(1);elsereturn(0);}voidCreatAjacentMatrix(int*array,intn)//创建邻接矩矩阵(n行n列){inta;inti,j,flag=0;printf(请输入一个%d行%d列的关于图的邻接矩阵:\n,n,n);for(i=0;in;i++)for(j=0;jn;j++){scanf(%d,&a);*(array+i*n+j)=a;计算机科学与工程学院数据结构上机实验5}}voidPrintAjacentMatrix(int*array,intn){inti,j;for(i=0;in;i++){for(j=0;jn;j++)printf(%5d,*(array+i*n+j));printf(\n);}}voidCreatAdjList(int*array,intn,ALGraph*G)//将邻接矩阵导出为图的邻接表形式{inti,j;ArcNode*p;//表结点G-vexnum=n;//初始化顶点数G-vertices=(VNode*)malloc((n+1)*sizeof(VNode));//头结点数组,开辟n+1长度的数组空间for(i=1;i=n;i++)//初始化头结点数组{G-vertices[i].data=i;G-vertices[i].firstarc=NULL;}//////////for(i=0;in;i++)for(j=0;jn;j++){if(*(array+i*n+j)==1){p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j+1;p-nextarc=G-vertices[i+1].firstarc;G-vertices[i+1].firstarc=p;}}}voidFindInDegree(ALGraphG,int*indegree)//对顶点求入度{inti,j;ArcNode*p;for(i=1;i=G.vexnum;i++)indegree[i]=0;//indispensablefor(i=1;i=G.vexnum;i++)//对每个结点跑完整个邻接表计算机科学与工程学院数据结构上机实验6for(j=1;j=G.vexnum;j++)for(p=G.vertices[j].firstarc;p;p=p-nextarc)if(G.vertices[i].data==p-adjvex)//==indegree[i]++;}intTopologicalSort(ALGraphG)//拓扑排序算法{//有向图采用邻接表存储结构//若G无回路，则flag=0,输出G的顶点的一个拓扑序列,否则给出该有向图有回路的提示.inti,count,k;int*indegree=(int*)malloc((G.vexnum+1)*sizeof(int));SqStackS;ArcNode*p;FindInDegree(G,indegree);//对顶点求入度indegree[G.vexnum]initialStack(&S);//为避免重复检测入度为0的顶点，可另设一栈暂存放所有入度为0的顶点for(i=1;i=G.vexnum;i++)if(!indegree[i])Push(&S,i);//0入度点进栈count=0;//对输出顶点计数，作为判断是否有回路的根据while(!StackEmpty(&S)){Pop(&S,&i);printf(%d,i);//输出i号顶点并计数count++;for(p=G.vertices[i].firstarc;p;p=p-nextarc){k=p-adjvex;//表结点的数据域，即对i号顶点的每个邻接点的入度减1if(!(--indegree[k]))//若入度减少为0，则入栈Push(&S,k);}}if(countG.vexnum)//该有向图有回路return0;elsereturn1;}voidmain(){intn;int*A;ALGraphG;计算机科学与工程学院数据结构上机实验7printf(请输入你想创建的邻接矩矩阵的行列数(即顶点数):\n);scanf(%d,&n);A=(int*)malloc(n*n*sizeof(int));CreatAjacentMatrix(A,n);printf(输出该图的邻接矩阵A:\n);PrintAjacentMatrix(A,n);CreatAdjList(A,n,&G);printf(该有向图的一个拓扑排序结果如下所示:\n);if(TopologicalSort(G))printf(\n);elseprintf(该有向图有回路，所以无法拓扑排序!\n);}实验内容计算机科学与工程学院数据结构上机实验83.测试用例：1,当输入一有向图的邻接矩阵A={0,1,1；0,0,0；0,1,0}时程序运行结果如下：经检验该有向图的拓扑排序结果确实为132。2.当输入有向图的邻接矩阵A={0,1,1,1；0,0,0,0；0,0,0,1；0,1,0,0}时运行结果如下：经检验，拓扑排序确实为1342.3.当输入有向图的邻接矩阵A={0,1,1,1；0,0,0,0；1,0,0,1；0,1,0,0}时运行结果如下：计算机科学与工程学院数据结构上机实验9由于该图无入度为零的节点，所以拓扑排序失败！实验内容计算机科学与工程学院数据结构上机实验104.实验总结：在这次实验的的过程当中确实发现很多问题，特别是拓扑排序算法的实现，另外在每次删除节点的时候，剩余结点该怎样处理，该怎样存储，确实花费了太多精力，不过现在才发现老师的课件还是非常重要，里面涉及到了很多算法，对于我们的学习起到了很重要的作用。对于本次实验最大的感慨就是我们要多实践，不能因为一次失败了而失去了信心，要学会越挫越勇，另外发现问题的同时，注重思考才是最重要的，在不断地思考过程中，我们才会学的更多。