拓扑排序

拓扑排序 xx学院 一、问题分析和任务定义 本次课程设计的题目是：选择合适的数据结构表示图，在此基础上实现拓扑排序算法。 问题分析如下： 关于拓扑排序的概念：对于有向图G=(V,VR)， V中顶点的线性序列（vi1, vi2, vi3 …，vin）称为拓扑序列。该序列必须满足如下条件： 对序列中任意两个顶点vi、vj，若在G 中有一条从vi到vj的路径，则在序列中vi必排在vj之前。构造有向图的一个拓扑序列的过程称为拓扑排序。在AOV网中,若不存在回路,则所有活动可排成一个线性序列,使得每个 活动的所有前驱活动都排在该活动的前面,那么该序列为拓扑序列.而且拓扑序列不是唯一的，对AOV网不一定都有拓扑序列。在搞清楚了拓扑排序的前提下，下一部是考虑选择合适 的数据结构表示图，这有很多种方法：比如，利用邻接表、利用邻接矩阵、利用生成树等等。 本程序设计选取的是用邻接表的存储结构。具体的设计如下： 1、 设计的输入数据的形式和范围 首先是输入要排序的顶点数和弧数，都为整型正整数，中间用分隔符隔开；再输入各顶 点的值，为整型数字，即正负数都行，中间用分隔符隔开；然后输入各条弧的两个顶点的值， 先输入弧头，再输入弧尾，中间用分隔符隔开，输入值只能是开始输入的顶点值，否则系统 会提示输入的顶点值不正确，请重新输入，只要继续输入正确的值就行，系统不会退出该程 序。 2、 设计的输出数据的形式和范围 首先输出建立好的邻接表，然后是最终各个顶点的入度数，再是输出拓扑排序的序列， 并且每输出一个顶点，就会输出一次各个顶点的入度数。这些数据都为整型数字。 3、 算法程序所能达到的功能 由于该程序的要求是拓扑排序，所以算法的功能就是要输出拓扑序列，在一个有向图中， 若用顶点表示活动，有向边表示活动间先后关系，那么输出的拓扑序列就表示各顶点间的关 系。为了反映出各顶点的存储结构，设计输出它的邻接表，并且输出各顶点的入度数 。 4、测试用的数据 2 3 2 3 1 7 4 1 4 5 5 6 6 图1 .AOV网 图2 .AOV网 设计如下两种测试数据： 4.1可以输出拓扑排序的例子： 如图1，输入顶点数和弧数6 8，再输入顶点值1 2 3 4 5 6，依次输入存在弧的两个顶点的值1和2，2和3，3和4，1和6，6和5，2和5，6和3，5和4。则建立的邻接表为: [1]-->[6]-->[2] 第1个点的入度为0 [2]-->[5]-->[3] 第2个点的入度为1 1 [3]-->[4] 第3个点的入度为2 [4] 第4个点的入度为2 [5]-->[4] 第5个点的入度为2 [6]-->[3]-->[5] 第6个点的入度为1 进行拓扑排序输出顺序为:1 2 6 5 3 4排序成功。 4.2不可以输出拓扑排序的例子： 如图2，输入顶点数和弧数7 10，再输入顶点值1 2 3 4 5 6 7，依次输入存在弧的两个顶点的值1和2，2和3，3和4，5和6，5和1，6和4，7和5，2和7，7和3，7和6。则建立的邻接表为: [1]-->[2] 第1个点的入度为1 [2]-->[7]-->[3] 第2个点的入度为1 [3]-->[4] 第3个点的入度为2 [4] 第4个点的入度为2 [5]-->[1]-->[6] 第5个点的入度为1 [6]-->[4] 第6个点的入度为2 [7]-->[6]-->[3]-->[5] 第7个点的入度为1 进行拓扑排序输出顺序为:排序失败 二、概要设计和数据结构的选择 根据以上的设计数据结构选择如下： 1、 算法中用到的所有各种数据类型的定义 在该程序中选择使用邻接表作为图的存储结构，因为这种存储结构简单容易理解。首先， 要定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数， 其中根据要求输入图的顶点数和边数，并根据要求设定每条边的起使位置，构造邻接表，依 次的将顶点插入到邻接表中。拓扑排序的函数在该函数中首先要对各个顶点求入度，其中要 用到求入度的函数，为了避免重复检测入度为零的顶点，设置了一个辅助栈，因此要定义顺 序栈类型，以及一系列栈的函数：初始化栈，入栈，出栈，判断栈是否为空。 2、 各程序模块之间的层次调用关系 本程序主要有三大部分组成：第一部分是void CreatGraph(ALGraph *G)函数构建图，用邻接表存储。这个函数中没有调用子函数。第二部分是void TopologicalSort(ALGraph G) 输出拓扑排序函数，在这个函数中首先调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1]；然后设置了一个辅助栈，调用InitStack(&S)初始化栈 ，再调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不空时，调用Pop(&S,&n) 输出栈中的顶点并将该含该顶点（起始顶点）的边都删除，入度indegree[k]--，当输出某一入度为0的顶点时，便将它从栈中删除。第三部分是主函数，先后调用void CreatGraph(ALGraph *G)函数构建图、void TopologicalSort(ALGraph G)输出拓扑排序函数从而实现整个程序。 2 3、 设计的主程序的 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 开始 调用建图函数 输入顶点数、弧 数、顶点值 Y输入存在弧的两个顶点 n > G->vexnum || m > G->vexnum N 输出邻接表 求入度 初始化栈 输出各顶点的入度建零入度顶点栈S， 入度为0者进栈 !StackEmpty(&S)判断并输出相应信息N Y Pop(&S,&n) 结束 Np=G.vertices[n].firstarc p!=NULL Y k=p->adjvex !(--indegree[k])p=p->nextarc NY Push(&S,k); 图 3. 主程序的流程 3 三、详细设计和编码： 主要分为编写算法和各程序模块代码、实现概要设计中定义所有数据类型和源程序这几 点： 1、编写算法和各程序模块代码 程序中个函数算法思想如下： 1.1 void InitStack(SqStack *S) 初始化栈，将栈的空间设为STACK_INIT_SIZE。 1.2 int Pop(SqStack *S,ElemType *e) 出栈操作，若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。 1.3 void Push(SqStack *S,ElemType e) 进栈操作,插入元素e为新的栈顶元素。 1.4 int StackEmpty(SqStack *S) 判断栈是否为空，语句if(S->top==S->base)判断若栈不空，则删除S的栈顶元素，并返回OK；否则返回ERROR。 1.5 void CreatGraph(ALGraph *G) 构建图，用邻接表存储，首先定义邻接表指针变量，输入顶点数和弧数，初始化邻接表， 将表头向量中的每个域置空，输入存在弧的点集合，当输入顶点值超出输入值的范围就会出 错，依次插入进邻接表，最后输出建立好的邻接表 1.6 void FindInDegree(ALGraph G,int indegree[]) 求入度操作，设一个存放各顶点入度的数组indegree[ ]，然后indegree[i]=0赋初值， for循环indegree[]++，存储入度数。 1.7 void TopologicalSort(ALGraph G) 输出拓扑排序函数。总的思路是若G无回路,则输出G的顶点的一个拓扑序列并返回OK, 否则返回ERROR。首先基于邻接表的存储结构入度为零的顶点即为没有前驱的顶点， 我们 可以附设一个存放各顶点入度的数组，调用FindInDegree(G,indegree)对各顶点求入度indegree[0..vernum-1]；然后为了避免重复检测入度为零的顶点，设置了一个辅助栈，调 用InitStack(&S)初始化栈 ，再调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不空时，调用Pop(&S,&n) 输出栈中的顶点并将该含该顶点（起始顶点）的边都删除，入 度indegree[k]--，当输出某一入度为0的顶点时，便将它从栈中删除。 2、实现概要设计中定义所有数据类型和源程序 #define MAX_VEXTEX_NUM 20//定义顶点最大数值为30 #define STACK_INIT_SIZE 100//定义栈的大小为100 #define STACKINCREMENT 10//定义栈的增量为10 typedef int ElemType;// 定义栈顶元素类型 typedef struct ArcNode {int adjvex;//该弧所指向的顶点的位置 struct ArcNode *nextarc;// 指向下一条弧的指针 }ArcNode;//表结点 typedef struct VNode {int data;//顶点信息 ArcNode *firstarc;//表结点的地址,指向该顶点的弧的指针 }VNode,AdjList[MAX_VEXTEX_NUM];//头结点 4 typedef struct {AdjList vertices; int vexnum, arcnum;// 图的顶点数和弧数 }ALGraph;//定义图 typedef struct //建栈 {ElemType *base;// 在栈构造之前的指针 ElemType *top;// 栈顶指针 int stacksize;//定义所分配的存储空间 }SqStack; // 顺序栈 四、上机调试 主要分为 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 程序调试过程中遇到的错误及问题的解决、算法的时间和空间性能分析、 算法优化的经验和体会这几点： 1、记录程序调试过程中遇到的错误及问题的解决 在调试初期，我遇到了无法找到入度初始值得问题，经过修改后，设置了一个辅助栈。 在编程过程中，对指针的运用还是很模糊，加深了对指针的了解，认识到指针在各种算法中 使用的重要性。在void TopologicalSort(ALGraph G)函数中，开始设计时没考虑要输入顶点值，直接进入到输入存在弧的两顶点，但是这样看起来程序并不完整，于是加入输入顶点 值的几条语句for(i=1;i<=G->vexnum;i++) {scanf("%d",&G->vertices[i].data); G->vertices[i].firstarc=NULL;} 其中i<=G->vexnum的范围开始没设好，输出值出错，改过后输出才正确。另外，返回值的设置0、1很容易弄错，于是在程序的头文件中加上#define OK 1，#define ERROR 0两句定义，返回OK 、ERROR就更加直观了。 2、算法的时间和空间性能分析 拓扑排序实际上是对邻接表表示的图G进行遍历的过程，每次访问一个入度为0的顶 点。若图G中没有回路，则需要扫描邻接表中的所有边接点，再加上在算法开始时，为建 立入度数组D需要访问表头向量中的每个域和其单链表中的每个接点，所以此算法的时间 复杂度为O（n+e）。 3、算法优化的经验和体会 优化：在拓扑排序的函数中，加入for (i=1;i<=G.vexnum;i++) {printf("第%d趟排序第%d 个点的入度为%d \n",j,i,indegree[i]);}j++;}输出各顶点入栈时每一趟的入度情况，即在每输出一个顶点时输出各顶点的入度情况。在各自函数中加入的存储分配失败的考虑，使整 个程序看起来更完整。 体会：完成这个实现拓扑排序的设计，第一，要选择合适的思想方法。选择合适的结构图， 我选择的是邻接表存储结构，来实现拓扑排序。第二，要进行算法研究。选择正确的算法更 是关键。通过查找 资料 新概念英语资料下载李居明饿命改运学pdf成本会计期末资料社会工作导论资料工程结算所需资料清单 和自己进行整理，写出了邻接表的基本算法思想，在此基础上进行拓 扑排序。然后再写出拓扑排序的算法思想，为以后的程序的完成做准备。第三，算法思想完 成以后，就进入最关键的程序设计阶段，首先，需要定义未知函数，其次，需要了解调用哪 些函数来完成程序。对于我这个程序，我调用了栈的一系列函数，构造有向图的函数，以及 构造邻接表的函数，添加数组帮助存储。第四，在程序的书写过程中，书写顺序也是问题。 在实现拓扑排序的这个程序中，首先要编写子函数，利用栈的存储运算，再进行图的构造， 构造邻接表，然后编写拓扑排序函数，输出拓扑排序。最后是主函数的编写。 五、用户使用说明 5 要建立一个有向图顶点之间的拓扑序列，用户请按如下说明进行操作： 第一步：统计图中顶点数目及弧的数目，对顶点进行编号，并写出顶点之间的先后顺序。 第二步：运行程序，输入顶点数目和弧的数目，中间用分隔符隔开，回车。 第三步：输入各顶点的值，中间用分隔符隔开，回车。 第四步：按要求输入各条弧的两个顶点的值，先输入弧头，再输入弧尾，中间用分隔符隔开， 输入完毕回车，系统就会依次输出邻接表，各顶点的入度数，排序成功输出拓扑序 列，或者输出排序失败。 第五步：在执行第四步输入时，如果输入了错误的顶点，系统将会提示输入错误请重新输入。 六、测试结果 2 2 3 3 1 4 1 4 6 5 5 6 图1.AOV网 图2.AOV网 例如图1所示的AOV网运行后截图如下： 6 例如图2所示的AOV网运行后截图如下： 七、参考书目 1、自编，数据结构与算法实验和课程设计指导书，本系精品课程建设组。 2、徐孝凯，数据结构实用教程，北京：清华大学出版社，1999年12月第1版。 3、严蔚敏等，数据结构题集（c语言），北京：清华大学出版社，1999年2月第1版。 4、李春葆，数据结构习题与解析（c语言），北京：清华大学出版社，2000年1月第1版。 5、王立柱，《c语言与数据结构》，北京：清华大学出版社, 2003年6月第1版。 八、附录：带注释的源程序 #include #include #define MAX_VEXTEX_NUM 20//定义顶点最大数值为30 #define M 20 #define STACK_INIT_SIZE 100//定义栈的大小为100 #define STACKINCREMENT 10//定义栈的增量为10 #define OK 1 #define ERROR 0 typedef int ElemType;// 定义栈顶元素类型 typedef struct ArcNode{ int adjvex;//该弧所指向的顶点的位置 struct ArcNode *nextarc;// 指向下一条弧的指针 }ArcNode;//表结点 7 typedef struct VNode{ int data;//顶点信息 ArcNode *firstarc;//表结点的地址,指向该顶点的弧的指针 }VNode,AdjList[MAX_VEXTEX_NUM];//头结点 typedef struct{ AdjList vertices; int vexnum, arcnum;// 图的顶点数和弧数 }ALGraph; typedef struct {//建栈 ElemType *base;// 在栈构造之前的指针 ElemType *top;// 栈顶指针 int stacksize;//定义所分配的存储空间 }SqStack; // 顺序栈 void InitStack(SqStack *S) {//初始化栈 S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));//构造空栈之前 的指针 if(!S->base)//存储分配失败 { printf("初始化出错，退出"); exit(1); } S->top=S->base;//空栈之前的指针赋给头指针 S->stacksize=STACK_INIT_SIZE;//栈的空间设为STACK_INIT_SIZE } int Pop(SqStack *S,ElemType *e) {//出栈操作 if(S->top==S->base)//栈空返回OK { return ERROR; } *e=*--S->top;//删除S的栈顶元素 return 0; } void Push(SqStack *S,ElemType e) {//进栈操作,插入元素e为新的栈顶元素 if(S->top-S->base>=S->stacksize)// 栈满，追加存储空间 { S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType)); if(!S->base) //存储分配失败 { printf("进栈出错，退出"); exit(1); } 8 S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *S->top++=e; } int StackEmpty(SqStack *S) {//判断栈是否为空 if(S->top==S->base)//若栈不空，则删除S的栈顶元素，并返回OK；否则返回ERROR return OK; else return ERROR; } void CreatGraph(ALGraph *G) {//构建图，用邻接表存储 int m, n, i; ArcNode *p;//定义邻接表指针变量 printf("请输入顶点数和弧数:"); scanf("%d%d",&G->vexnum,&G->arcnum);//输入顶点数和弧数 printf("请输入%d个顶点值:",G->vexnum); for(i=1;i<=G->vexnum;i++) // 构造顶点向量 { scanf("%d",&G->vertices[i].data); G->vertices[i].firstarc=NULL; } for (i=1; i<=G->arcnum; i++) //输入存在弧的点集合 { printf("请输入存在弧的两个顶点的值:"); scanf("%d%d",&n,&m); while (n > G->vexnum || m > G->vexnum) {//当输入顶点值超出输入值的范围就会出错 printf("输入的顶点值不正确 请重新输入:"); scanf("%d%d",&n,&m); } p=(ArcNode*)malloc(sizeof(ArcNode)); if(p==NULL) { printf("出错，退出");//存储分配失败 exit(1); } p->adjvex=m; p->nextarc=G->vertices[n].firstarc;//依次插入进邻接表 G->vertices[n].firstarc=p; } printf("建立的邻接表为:\n"); //输出建立好的邻接表 for(i=1;i<=G->vexnum;i++) { 9 printf("[%d]",G->vertices[i].data); for(p=G->vertices[i].firstarc;p;p=p->nextarc) printf("-->[%d]",p->adjvex); printf("\n"); } } void FindInDegree(ALGraph G,int indegree[]){//求入度操作 int i; for (i=1;i<=G.vexnum;i++) { indegree[i]=0;//赋初值 } for (i=1;i<=G.vexnum;i++) { while(G.vertices[i].firstarc) { indegree[G.vertices[i].firstarc->adjvex]++; G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc; } } } void TopologicalSort(ALGraph G) {//输出拓扑排序函数。若G无回路,则输出G的顶点的 一个拓扑序列并返回OK, 否则返回ERROR。 int indegree[M]; int i,j=1, k, n; int count=0; ArcNode *p; SqStack S; FindInDegree(G,indegree);//对各顶点求入度indegree[0..vernum-1] InitStack(&S);//初始化栈 for (i=1;i<=G.vexnum;i++) { printf("第%d个点的入度为%d \n",i,indegree[i]); } printf("\n"); for(i=1;i<=G.vexnum;i++)// 建零入度顶点栈S { if(!indegree[i]) Push(&S,i);//入度为0者进栈 } printf("进行拓扑排序输出顺序为:\n"); //输出结果 while(!StackEmpty(&S))//栈不空时 { Pop(&S,&n); 10 printf("%4d\n",G.vertices[n].data); count++;//输出i号顶点并计数 for(p=G.vertices[n].firstarc;p!=NULL;p=p->nextarc) {//对i号顶点的每个邻接点的入度减1 k=p->adjvex; if(!(--indegree[k]))//若入度减为0,则入栈 { Push(&S,k); } } for (i=1;i<=G.vexnum;i++)//输出各顶点入栈时每一趟的入度情况 { printf("第%d趟排序第%d个点的入度为%d \n",j,i,indegree[i]); } j++; } printf("\n"); if(count