拓扑排序课程设计报告

1、Word 资料.数据结构课程设计设计题目： 有向图拓扑排序_专业：信息与计算科学_学号：021240616_姓名：黄秋实_指导教师：_2013年11月28日Word 资料.数据结构课程设计-拓扑排序一需求分析1.问题描述本次课程设计题目是：用邻接表构造图 然后进行拓扑排序，输出拓扑排序 序列拓扑排序的基本思想为：1）从有向图中选一个无前驱的顶点输出；2）将此顶点和以它为起点的弧删 除；3）.重复 1）,2）直到不存在无前驱的顶点；4）.若此时输出的顶点数小于有向 图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑 序列。2.拓扑排序 有向图拓朴排序算法的基本步骤如下：从图中

2、选择一个入度为 0 的顶点，输出该顶点；从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度-1）；重复执行、直到所有顶点均被输出， 拓朴排序完成或者图中再也没有入度为 0 的顶点（此种情况说明原有向图含有 环）。3 基本要求（1）输入的形式和输入值的围；首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输 入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值， 先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶 点值否则系统会提示输入的值的顶点值不正确， 请重新输入，只要继续输入正 确的值就行。(2) 输出的形式；Word 资料.首先输

3、出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序 列，并且每输出一个顶点，就会输出一次各顶点的入度数。(3) 程序所能达到的功能；因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列， 在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出 的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。二概要设计1. 算法中用到的所有各种数据类型的定义在该程序中用邻接表作为图的存储结构。 首先，定义表结点和头结点的结构 类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入 图的顶点和边数，并根据要求设定每条边的起始位

4、置，构建邻接表依次将顶点插 入到邻接表中。拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数， 为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型， 以及栈的函数：入栈，出栈，判断栈是否为空。2. 各程序模块之间的层次调用关系第一部分， void ALGraph *G 函数构建图， 用邻接表存储。 这个函数没有调 用函数。第二部分，void TopologicalSort(ALGraph *G)输出拓扑排序函数，这个函数首先调用 FindInDegree(G,indegree)对各顶点求入度 indegree0 - vernum-1;然 后Word 资料.设

5、置了一个辅助栈，调用 InitStack(&S)初始化栈，在调用 Push(&S,i 入度为 0 者进栈，while(!StackEmpty(&S)栈不为空时，调用 Pop(&sS,&n)输出栈中顶点并 将以该顶点为起点的边删除，入度 indegreek-,当输出某一入度为 0 的顶点时， 便将它从栈中删除。第三部分，主函数，先后调用 void CreatGraph(ALGraph *G)函数构建图、 voidTopologicalSort(ALGraph *G)函数输出拓扑排序实现整个程序。3.设计的主程序流程(见附页)三详细设计(实现概要设计中定义的

6、所有数据类型，对每个操作写出伪码算法；对主 程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为；按照 伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；写出出函数和过程的调用关系。)1实现概要设计中定义的所有数据类型#i nclude#i nclude#defi ne MAX_VEXTEX_NUM 100#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10#defi ne OK 1#defi ne M 100#defi ne ERROR 0typedef int ElemType;Word 资料.typedef str

7、uct ArcNodeint adjvex;struct ArcNode *n extarc;ArcNode;typedef struct VNodeint data;ArcNode *firstarc;VNode,AdjListMAX_VEXTEX_NUM;typedef structAdjList vertices;int vex num, arcnum;ALGraph;typedef structElemType *base;ElemType *top;int stacksize;SqStack;2.算法和各模块的代码Word 资料.程序中各函数算法思想如下：2.1void In itS

8、tack(SqStack *S)初始化栈将栈的空间设为 STACK-INIT-SIZ 巳2.2int Pop(SqStack *S,ElemType *e)出栈操作，若站不空，删除 S 的栈顶元素，用 e 返回其值，并返回 0K；否贝 U 返回 ERROR2.3void Push(SqStack *S,ElemType e)进栈操作，插入元素 e 为新的栈顶元素。2.4int StackEmpty(SqStack *S)判断栈是否为空，语句 if (S-top=S-base )判断，若栈不为空，则删除 S的栈顶元素，并返回 0K;否则返回 ERROR2.5void CreatGraph (AL

9、Graph *G)构建图，用邻接表存储，首先定义邻接表指针变量，输入顶点数和弧数，初始化邻接表，将表头向量域置空，输入存在弧的点集合，当输入顶点值超出输 入值的围就会出错，否则依次插入进邻接表，最后输出建立好的邻接表。2.6void Fi ndl nDegree(ALGrap G, i nt in degreee)求入度操作，设一个存放各顶点入度的数组indegreee，然后indegreeei=0 赋初值，for 循环 indegreee+，存储入度数。Word 资料.2.7void TopologicalISort(ALGraph G)输出拓扑排序函数。其思路是若 G 无回路，则输出 G

10、的顶点的一个拓扑序列并返回 OK，否则返回 ERROR 首先由于邻接表的存储结构入度为零的顶点即为没有前驱的顶点，我们可以附设一个存放个顶点入度的数组，调用FindlnDegree( G, indegreee)对各顶点求入度；为了避免重复检测入度为零0 的顶点，设置一个栈，调用 InitStack(&S)初始化栈，在调用 Push(&S,i)入度为 0 者 进栈，while(!StackEmpty(&S)栈不为空时，调用 Pop(&sS,&n)输出栈中顶点并将 以该顶点为起点的边删除，入度 indegreek-,当输出某一入度为 0 的顶点时， 便将它从

11、栈中删除。3.算法的时间复杂度和空间复杂度拓扑排序实际是对邻接表表示的图 G 进行遍历的过程，每次访问一个入度 为零的顶点，若图 G 中没有回路，则需扫描邻接表中的所有边结点，在算法开 始时，为建立入度数组 D 需访问表头向量中的所有边结点，算法的时间复杂度 为 O(n+e)。四测试与分析对有向无环图【下图】进行拓扑排序。Word 资料.输入： D：iilc+jgXllJill exerI o回S3清输入顶点数和边数皿谱辎入存在边的两个顶点的序哥先输入弧屋，再输入弧头泊4崙金入存在边的两个顶点於序号,先输AW,再输入弧头注土 :諭入存在边的两个顶点的序号，先辎人弧尾，再输入弧头泊12崙俞入存任

12、边的两个顶点的序号，先轴A.弧童 再输人弧汨1 3清辎入存在边的两个顶点的序号，先辎人弧尾，再输入弧头曰3 iA4i+VJ的两个顶点的序号，先输人弧电 再输入弧头叮5清输入存在边的两个顶点的序号，先输人弧尾，再输入弧头胡7 7沽输入存在选的曲个顶点的序号，先5HAS屋，冉输入蛆头叮s:諭入存在边的两个顶点的序号，先输人弧尾，再输入弧头注 :諭人存在辺的的个顶点的序号.先辑冉输入英头叮7请输入存在边的两个顶点的序号，先输人弧尾，再输入弧头订B:諭人存在边的两个顶点战序号.先输人弧屋.再输丄弧Word 资料.:，件：十隔程DebJllllllfiME戶输入存在边的两介顶点的序号, 青输入存住边的两

13、个顶点的疗号:青输人存枉辺的两个顶点的序号. 请输入善在边的两彳顶点的序弓: 青输入存在边的两个顶点的JT号, 青输入存在边的两个顶点射序号：青输入存在边的两个顼点的序号.先辆扎弧星丸输入弧尾,先输人机屋*颔 入ME,先输人？馄. 先输人弧尾, 先輸入弧屋.冉辅A弧舟2再戦入弧头泊 再输入弧畑 再輸入弧畑 再辎入弧头汽 再输入弧光5再揄入弧头汀再输入弧畑再楡入弧头汕带输入存在边的两个顶点的序号，先输入弧尾， 青输入存在边的两个顶点的序环先输人孤屋* 盲输入存在边的两个腆点的序号，先输人弧尾，再人弧头汚 青输入存在边的两个顶点的序号，先输人魂再揄入弧头迄丄右制俞入序在边的两个顶点的序号，先输人弧

14、总 再入张头曲1211结果如下:五总结拓扑排序就是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v,若E(G),则u在线性序列中出现在v之前。在进行课程设计中，更好的认识了拓扑排序。理清了各个模块之间算法之间的条理。认 识了 伪代码(Pseudocode)是一种算法描述语言。使用伪代码的目的是为了使被描 述的算法可以容易地以任何一种 编程语言(Pascal,C,Java,etc)实现。因此，伪Word 资料.代码必须结构清晰、代码简单、可读性好，并且类似自然语言。介于自然语言与编程语言之间。它

15、是一种让人便于理解的代码。不依赖于语言的，用来表示程序执行过 程，而不一定能编译运行的代码。在数据结构 讲算法的时候用的很多。在设计中，我们遇到了程序正确，去卩对某些无向图无法进行拓扑排序的问题。多次对程序进行修改后，才可以进行拓扑排序。问题出在调用函数的错误理解，模块之 间的联系模糊不清。六附录：源程序：#i nclude#i nclude#defi ne MAX_VEXTEX_NUM 100#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10#defi ne OK 1#defi ne M 100#defi ne ERROR 0type

16、def int ElemType;typedef struct ArcNodeint adjvex;struct ArcNode *n extarc;ArcNode;typedef struct VNodeint data;ArcNode *firstarc;Word 资料.VNode,AdjListMAX_VEXTEX_NUM;typedef structAdjList vertices;int vex num, arcnum;ALGraph;typedef structElemType *base;ElemType *top;int stacksize;SqStack;void In it

17、Stack(SqStack *);int Pop(SqStack *, ElemType *);void Push(SqStack *,ElemType );int StackEmpty(SqStack *);void CreatGraph(ALGraph *);void Fin di nDegree(ALGraph , int * );void TopologicalSort(ALGraph );void In itStack(SqStack *S)S-base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType);Word 资料.if(!S

18、-base)printf(存分配失败，请检查储存位置，再见);exit(1);S-top=S-base;S-stacksize=STACK_INIT_SIZE;int Pop(SqStack *S,ElemType *e)if(S-top=S-base)return ERROR;*e=*-S-top;return 0;void Push(SqStack *S,ElemType e)if(S-top-S-base=S-stacksize)S-base=(ElemTypeWord 资料.*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(Ele

19、mType);if(!S-base)printf(存分配失败，请检查储存位置，再见);exit(1);S-top = S-base+S-stacksize;S-stacksize+=STACKINCREMENT;*S-top+=e;int StackEmpty(SqStack *S)if(S-top=S-base)return OK;else return ERROR;void CreatGraph(ALGraph *G)int m, n, i;ArcNode *p;printf（请输入顶点数和边数:）;Word 资料.sea nf(%d%d,&G-vex num,&G-arc

20、 num);for (i = 1; i vex num; i+)G-verticesi.data = i;G-verticesi.firstarc = NULL;for (i = 1; i arc num; i+)printf(n 请输入存在边的两个顶点的序号，先输入弧尾，再输入弧头：);sca nf(%d%d,&n,&m);while (n G-vex num | m G-vex num)printf(输入的顶点序号不正确请重新输入:);sca nf(%d%d,&n,&m);p = (ArcNode*)malloc(sizeof(ArcNode);if (p = NULL)printf(存分配失败，请检查储存位置，再见);exit(1);p-adjvex = m;p-n extarc = G-vertices n.