拓扑排序课程设计报告 (2)

数学与计算机学院数据结构实验报告年级09数计学号2009432125 姓名刘宝成绩专业数电实验地点主楼401 指导教师苗秀芬实验项目拓扑排序实验日期10年12月24日一、实验目的1掌握图的存储结构及其基本操作，学会定义图的邻接表存储结构，并能在实际问题中灵活运用。

2掌握拓扑排序算法。

3、通过本实验的具体应用实例，灵活运用拓扑排序并进一步巩固队列/栈的运用。

二、实验问题描述1简介：用邻接表形式存储实验中的有向无环图，此有向无环图称为：AOV网，若网中每一个顶点都在他的拓扑排序中，则说明不存在环。

2步骤：①从AOV网中选出一个没有前驱的结点，并输出他；②从网中删除此结点，并且删除从该顶点发出的所有有向边（邻接点的入度-1）③重复以上两步，直到途中不存在入度为0的顶点为止三、实验步骤1、实验问题分析（1）顶点表typedef struct//顶点表结点{int in;//入度int vertex;//顶点域edgenode * firstedge;//边表头指针}vertexnode;（2）边表typedef struct node //边表结点{int adjvex;//邻接点域struct node * next;//指向下一个邻接点的指针域}edgenode;（3）以邻接表类型存储的图类型typedef struct{Adjlist adjlist; //邻接表int vnum,Enum; //顶点数和边数}Algraph;2、功能（函数）设计（1）建立一个以邻接表存储的有向图函数原型：void creatalgraph(Algraph *G)（2）拓扑排序函数原型：void TopoSort(Algraph *G)四、实验结果（程序）及分析1、实验主要模块代码（带注释！）或模块的流程图(1)建立一个以邻接表存储的有向图void creatalgraph(Algraph *G)//创建邻接链表{int i,k,j;edgenode *s;cout<<"该AOV网的顶点数和边数："<<endl;cin>>G->vnum>>G->Enum; //读入顶点数和边数cout<<"请输入顶点信息："<<endl;for(i=0;i<G->vnum;i++) //建立有vnum个顶点的顶点表{cin>>G->adjlist[i].vertex; //读入顶点信息G->adjlist[i].in=0;G->adjlist[i].firstedge=NULL; //顶点的边表头指针设为空}cout<<"请输入边的信息："<<endl; //for(k=0;k<G->Enum;k++) //建立边表{cout<<"依次输入每一条边："<<endl;cout<<"从";cin>>i;cout<<"邻接到";cin>>j;cout<<endl;//读入边<vi,vj>的顶点对应的序号s=new edgenode; //生成新的边表结点s->adjvex=j; //邻接点的序号为js->next=G->adjlist[i].firstedge; //将新边表结点s插入到顶点vi的边表头部G->adjlist[i].firstedge=s;}}(2)拓扑排序int toposort(Algraph *G){int i,j,k;int m=0,top;edgenode *ptr;top=-1;for(i=0;i<G->vnum;i++)if(G->adjlist[i].in==0){ G->adjlist[i].in=top;top=i;}while(top!=-1){j=top;top=G->adjlist[top].in;cout<<G->adjlist[j].vertex<<endl;m++;ptr=G->adjlist[j].firstedge;while(ptr!=NULL){k=ptr->adjvex;G->adjlist[k].in--;if(G->adjlist[k].in==0){G->adjlist[k].in=top;top=k;}ptr=ptr->next;//头插入}}if(m<G->vnum){cout<<"此图中存在环！无法进行拓扑排序"<<endl;return 0;//返回错误代码0}elsereturn 1;//成功返回1}2、测试数据3、调试过程中出现的问题以及解决策略。

实验题目：图的应用实验目的：（1）熟练掌握图的基本存储方法；（2）熟练掌握图的深度优先和广度优先搜索方法；（3）掌握AOV网和拓扑排序算法；（4）掌握AOE网和关键路径。

实验内容：拓扑排序。

任意给定一个有向图，设计一个算法，对它进行拓扑排序。

拓扑排序算法思想：a.在有向图中任选一个没有前趋的顶点输出；b.从图中删除该顶点和所有以它为尾的弧；c.重复上述a、b，直到全部顶点都已输出，此时，顶点输出序列即为一个拓朴有序序列；或者直到图中没有无前趋的顶点为止，此情形表明有向图中存在环。

设计分析：为实现对无权值有向图进行拓扑排序，输出拓扑序列，先考虑如何存储这个有向图。

拓扑排序的过程中要求找到入度为0的顶点，所以要采用邻接表来存储有向图，而要得到邻接表，则先要定义有向图的邻接矩阵结构，再把邻接矩阵转化成邻接表。

在具体实现拓扑排序的函数中，根据规则，当某个顶点的入度为0（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，为了避免重复检测入度为0的顶点，设立一个栈St，以存放入度为0的顶点。

源程序代码：#include<stdio.h>#include<stdlib.h>#define MAXV 10 // 最大顶点个数typedef struct{int edges[MAXV][MAXV]; // 邻接矩阵的边数组int n; // 顶点数}MGraph;typedef struct ANode{int adjvex; // 该弧的终点位置struct ANode * nextarc; // 指向下一条弧的指针}ArcNode;typedef struct{int no; // 顶点信息int count; // 顶点入度ArcNode * firstarc; // 指向第一条弧}VNode, AdjList[MAXV];typedef struct{AdjList adjlist; // 邻接表int n; // 图的顶点数}ALGraph;void MatTolist(MGraph g, ALGraph * &G){int i, j, n=g.n;ArcNode * p;G = (ALGraph *)malloc(sizeof(ALGraph));for (i=0; i<n; i++)G->adjlist[i].firstarc = NULL;for (i=0; i<n; i++)for (j=n-1; j>=0; j--)if (g.edges[i][j]!=0){p=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex = j;p->nextarc = G->adjlist[i].firstarc;G->adjlist[i].firstarc = p;}G->n=n;}void TopSort(ALGraph * G){int i,j,flag=0,a[MAXV];int St[MAXV], top = -1; // 栈St的指针为topArcNode * p;for (i=0; i<G->n; i++) // 入度置初值为0 G->adjlist[i].count = 0;for (i=0; i<G->n; i++) // 求所有顶点的入度{p=G->adjlist[i].firstarc;while (p!=NULL){G->adjlist[p->adjvex].count++;p=p->nextarc;}}for (i=0; i<G->n; i++)if (G->adjlist[i].count==0) // 入度为0的顶点进栈{top++; St[top] = i;}while (top>-1) // 栈不为空时循环{i = St[top]; top--; // 出栈a[flag++]=i; // 输出顶点p=G->adjlist[i].firstarc; // 找第一个相邻顶点while (p!=NULL){j = p->adjvex;G->adjlist[j].count--;if (G->adjlist[j].count==0){top++; St[top] = j; // 入度为0的相邻顶点进栈}p = p->nextarc; // 找下一个相邻顶点}}if (flag<G->n)printf("该图存在回路，不存在拓扑序列!\n");else{printf("该图的一个拓扑序列为:");for(i=0; i<flag; i++)printf("%d", a[i]);printf("\n");}}void main(){int i, j;MGraph g;ALGraph * G;G=(ALGraph *)malloc(sizeof(ALGraph));printf("请输入图的顶点数:");scanf("%d", &g.n);printf("请输入图的邻接矩阵:\n");for(i=0; i<g.n; i++)for(j=0; j<g.n; j++)scanf("%d", &g.edges[i][j]);MatTolist(g, G);TopSort(G);} 测试用例：对图7-1所示的有向图进行拓扑排序的测试结果如下：图7-1图7-2程序执行界面，提示输入图的顶点数，输入之后又提示输入其邻接矩阵，对图7-1所示的有向图的邻接矩阵输入如图7-2所示。

求拓扑序列排序课程设计一、教学目标本课程的教学目标是让学生掌握拓扑序列排序的基本概念、原理和应用，培养学生运用拓扑序列排序解决问题的能力。

具体包括以下三个方面的目标：1.知识目标：（1）理解拓扑序列排序的定义和性质；（2）掌握拓扑排序算法及其实现；（3）了解拓扑序列排序在实际应用中的重要性。

2.技能目标：（1）能够运用拓扑排序解决简单的问题；（2）能够运用图论知识分析和解决拓扑排序相关问题；（3）能够运用编程语言实现拓扑排序算法。

3.情感态度价值观目标：（1）培养学生对计算机科学的兴趣和热情；（2）培养学生团队合作、自主学习的能力；（3）培养学生运用所学知识解决实际问题的意识。

二、教学内容本课程的教学内容主要包括以下几个部分：1.拓扑序列排序的基本概念：图、顶点、边、度数、入度、出度等；2.拓扑排序的原理：拓扑排序的定义、拓扑排序的存在性、拓扑排序的算法；3.拓扑排序算法实现：深度优先搜索（DFS）算法、广度优先搜索（BFS）算法；4.拓扑排序的应用：任务调度、项目规划等实际问题。

三、教学方法为了达到本课程的教学目标，将采用以下几种教学方法：1.讲授法：通过讲解拓扑序列排序的基本概念、原理和应用，使学生掌握相关知识；2.讨论法：学生分组讨论拓扑排序算法实现和应用问题，培养学生的思考和表达能力；3.案例分析法：分析实际应用中的拓扑排序问题，让学生学会将理论知识应用于实际问题；4.实验法：安排拓扑排序算法的编程实验，培养学生的动手能力和实际问题解决能力。

四、教学资源为了支持本课程的教学内容和教学方法的实施，将准备以下教学资源：1.教材：《图论与算法导论》；2.参考书：《计算机网络》、《数据结构与算法》；3.多媒体资料：PPT课件、教学视频；4.实验设备：计算机、网络设备。

通过以上教学资源的使用，丰富学生的学习体验，提高学生的学习效果。

五、教学评估本课程的教学评估将采取多元化、全过程的方式进行，以全面、客观、公正地评价学生的学习成果。

数据结构拓扑排序实验报告正文：一、实验目的本实验旨在通过实现拓扑排序算法来加深对数据结构中图的相关概念的理解，掌握拓扑排序的具体步骤与实现方法。

二、实验原理拓扑排序是一种对有向无环图进行排序的算法，它可以将有向无环图的顶点按照线性的顺序排列出来，使得对于任何一个有向边(u, v)，都有顶点 u 在排列中出现在顶点 v 之前。

拓扑排序常用于表示图中的依赖关系，如任务调度、编译顺序等场景。

三、实验步骤1. 构建有向图根据实际需求构建有向图，可以使用邻接表或邻接矩阵等数据结构来表示有向图。

2. 执行拓扑排序算法利用拓扑排序算法对构建的有向图进行排序，可选择使用深度优先搜索（DFS）或广度优先搜索（BFS）等算法实现。

3. 输出排序结果将排序后的顶点按照线性的顺序输出，得到拓扑排序的结果。

四、实验结果与分析1. 实验数据以图 G = (V, E) 的顶点集合 V 和边集合 E，构建了如下的有向图：V = {A, B, C, D, E, F}E = {(A, C), (B, C), (C, D), (D, E), (E, F)}2. 拓扑排序结果经过拓扑排序算法的处理，得到的拓扑排序结果如下： A, B, C, D, E, F3. 结果分析可以看出，根据有向图的依赖关系，拓扑排序算法能够将顶点按照合理的顺序进行排序。

拓扑排序的结果可以作为图中顶点的执行顺序，具有重要的应用价值。

五、实验总结通过本次实验，我们深入学习了拓扑排序算法，并成功实现了拓扑排序的过程。

拓扑排序在图论和数据结构中具有广泛的应用，对于理解和解决与图相关的问题具有重要意义。

六、附件本文档没有涉及附件内容。

七、法律名词及注释本文档没有涉及法律名词及注释。

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：拓扑排序算法院（系）：计算机学院专业：计算机科学与技术（嵌入式系统方向）班级：14010105班学号：2011040101221姓名：王芃然指导教师：丁一军目录1 课程设计介绍 (1)1.1课程设计内容 (1)1.2课程设计要求 (1)2 课程设计原理 (2)2.1课设题目粗略分析 (2)2.2原理图介绍 (2)2.2.1 功能模块图 (2)2.2.2 流程图分析 (3)3 数据结构分析 (7)3.1存储结构 (7)3.2算法描述 (7)4 调试与分析 (12)4.1调试过程 (12)4.2程序执行过程 (12)参考文献 (14)附录（关键部分程序清单） (15)1 课程设计介绍1.1 课程设计内容由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

若在图一的有向图上人为的加一个表示V2<=V3的弧(“<=”表示V2领先于V3)则图一表示的亦为全序且这个全序称为拓扑有序,而由偏序定义得到拓扑有序的操作便是拓扑排序。

在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。

编写算法建立有向无环图，主要功能如下：1.能够求解该有向无环图的拓扑排序并输出出来；2.拓扑排序应该能处理出现环的情况；3.顶点信息要有几种情况可以选择。

1.2 课程设计要求1.输出拓扑排序数据外，还要输出邻接表数据；2.参考相应的资料，独立完成课程设计任务；3.交规范课程设计报告和软件代码。

2 课程设计原理2.1 课设题目粗略分析本课设题目要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个无环的有向图，是一类较有向图更一般的特殊有向图。

其功能要求及个人在写程序时对该功能的实现作如下分析：1. 将图以合适的方式存储起来。

图有多种存储方式，其中最常用的存储方式有图的邻接矩阵和邻接表。

拓扑排序实验报告一、引言拓扑排序是一种图论中重要的算法，用于对有向无环图（DAG）中的顶点进行排序。

在该实验中，我们将对拓扑排序的算法进行实现，并对其进行性能分析和评估。

二、实验目的1. 了解拓扑排序的基本概念和算法；2. 实现拓扑排序的算法；3. 进行性能分析和评估，探究其时间复杂度。

三、实验方法1. 根据给定的有向无环图构建邻接表；2. 使用深度优先搜索（DFS）算法实现拓扑排序；3. 对不同规模的图进行拓扑排序，并记录所用时间；4. 分析并评估算法的性能。

四、实验过程1. 构建邻接表：根据给定的有向无环图，我们首先构建它的邻接表表示。

邻接表中的每个节点表示一个顶点，其指针指向该顶点的所有后继节点。

2. 深度优先搜索拓扑排序：从图中选择一个未被访问过的顶点作为起始点，递归地遍历其所有后继节点，直到所有的顶点都被访问过。

通过递归的方式，可以得到一个拓扑排序的结果。

3. 性能分析和评估：我们使用不同规模的图进行拓扑排序，并记录所用的时间。

根据实验数据，分析算法的时间复杂度，并评估其性能。

五、实验结果我们使用了10个不同规模的有向无环图进行了拓扑排序，并记录了所用的时间。

实验结果表明，随着图规模的增加，算法的时间复杂度也随之增加。

具体结果如下：图规模时间(ms)5 0.00110 0.00350 0.012100 0.025250 0.067500 0.135750 0.2561000 0.3872000 0.8055000 2.016通过以上实验结果，我们可以看出，拓扑排序算法的时间复杂度约为O(n + m)，其中n为图中的顶点数，m为图中的边数。

实验结果与理论分析相符。

六、实验总结在本次实验中，我们实现了拓扑排序的算法，并进行了性能分析和评估。

通过实验结果可以看出，随着图规模的增加，算法的时间复杂度也随之增加。

拓扑排序算法是一种非常有用的算法，广泛应用于各个领域，例如编译器的依赖关系分析和任务调度等。

引言概述：在计算机科学领域，拓扑排序是一个经典的算法问题，用于解决有向无环图中节点的依赖关系排序问题。

通过拓扑排序，可以确定节点之间的先后顺序，从而确保在执行某些操作时不会出现冲突。

本实验报告旨在探讨和分析拓扑排序算法的实现过程和应用场景，以及拓扑排序在解决任务调度、编译器优化等问题中的作用。

正文内容：1. 算法原理1.1 定义拓扑排序是指对于一个有向无环图（DAG）中的节点，按照它们之间的依赖关系进行排序的过程。

在拓扑排序中，如果存在一条从节点 A 到节点 B 的有向边，那么在排序结果中，节点 A 必须在节点 B 之前。

1.2 算法过程拓扑排序算法的基本思想是不断地选择没有前驱节点的节点，并将其添加到排序结果中。

具体实现过程可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法。

1.3 算法示例假设有一个任务调度图，其中每个节点表示一个任务，节点之间的有向边表示任务之间的依赖关系。

拓扑排序算法可以按照任务之间的依赖顺序将任务排序，以确定它们的执行顺序。

2. 拓扑排序的应用场景2.1 任务调度拓扑排序可以用于解决任务调度问题。

在一个任务调度系统中，每个任务可能有多个前置任务，拓扑排序可以帮助确定任务的执行顺序，确保没有任务在其前置任务完成之前执行。

2.2 编译器优化在编译器优化过程中，拓扑排序可应用于解决指令调度问题。

指令调度是指在一个指令流中对指令进行重新排序，以提高执行效率。

通过拓扑排序，可以确定指令之间的依赖关系，避免出现冲突，从而优化编译器生成的指令流。

2.3 依赖关系管理在软件开发中，模块之间可能存在依赖关系。

拓扑排序可以帮助开发人员管理这些依赖关系，确保模块的顺序正确，减少错误和冲突的发生。

2.4 数据流分析拓扑排序还可以应用于数据流分析的算法中。

数据流分析是指对程序中变量的使用和定义关系进行分析，以便进行性能优化或错误检测。

拓扑排序可以帮助确定变量之间的依赖关系，从而更准确地进行数据流分析。

拓扑排序一、问题描述在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。

拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。

按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。

二、基本要求1、选择合适的存储结构，建立有向无环图，并输出该图；2、实现拓扑排序算法；3、运用拓扑排序实现对教学计划安排的检验。

三、算法思想1、采用邻接表存储结构实现有向图；有向图需通过顶点数、弧数、顶点以及弧等信息建立。

2、拓扑排序算法void TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈或队列实现。

考虑到教学计划安排的实际情况，一般先学基础课（入度为零），再学专业课（入度不为零），与队列先进先出的特点相符，故采用队列实现。

3、拓扑排序算法void TopologicalSort(ALGraph G)，大体思想为：1)遍历有向图各顶点的入度，将所有入度为零的顶点入队列；2)队列非空时，输出一个顶点，并对输出的顶点数计数；3)该顶点的所有邻接点入度减一，若减一后入度为零则入队列；4)重复2)、3)，直到队列为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。

4、要对教学计划安排进行检验，因此编写了检测用户输入的课程序列是否是拓扑序列的算法void TopSortCheck(ALGraph G)，大体思想为：1)用户输入待检测的课程序列，将其存入数组；2)检查课程序列下一个元素是否是图中的顶点（课程），是则执行3)，否则输出“课程XX 不存在”并跳出；3)判断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出；4)该顶点的所有邻接点入度减一；5)重复2)、3)、4)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。

拓扑排序实验报告第一点：实验背景及目的在计算机科学中，拓扑排序是一种针对有向无环图（DAG）的算法，其目的是对图中的所有节点进行排序，使得对于图中的每一条有向边(u,v)，节点u在排序中都出现在节点v之前。

拓扑排序的应用非常广泛，如任务调度、编译单元的生成等。

本实验的目的在于使学生理解和掌握拓扑排序的基本概念和方法，培养学生运用拓扑排序解决实际问题的能力。

通过实验，学生应能熟练使用拓扑排序算法对给定的有向无环图进行排序，并理解算法的时间复杂度。

第二点：实验原理与方法拓扑排序算法的基本原理是先找到所有入度为0的节点，将它们加入结果序列中，然后从图中删除这些节点以及它们的出边，之后再找到新的入度为0的节点，重复上述过程，直到所有节点都被加入结果序列中或者图中仍有节点存在。

如果图中仍有节点存在，则说明图中含有环，无法进行拓扑排序。

实验中，我们将使用深度优先搜索（DFS）算法来实现拓扑排序。

具体方法是，从图中的任意节点开始，进行深度优先搜索，每当访问一个节点时，就将它从图中删除，并将其入边所指向的节点入度减一。

当某个节点的入度变为0时，将其加入结果序列中。

重复这个过程，直到所有节点都被删除或者图中仍有节点存在。

以上就是拓扑排序实验报告的第一点和第二点内容，希望能对你有所帮助。

第三点：实验环境与工具为了完成拓扑排序的实验，我们需要准备以下环境和工具：1.编程语言：本实验可以使用C++、Java、Python等编程语言完成。

在这里，我们推荐使用Python，因为Python具有简洁的语法和强大的第三方库支持，非常适合进行算法实验。

2.开发环境：Python开发者可以使用PyCharm、VSCode等集成开发环境进行实验。

这些开发环境提供了代码高亮、调试、语法检查等功能，可以提高开发效率。

3.第三方库：在Python中，我们可能需要使用如matplotlib、networkx等第三方库来绘制图和进行图的算法分析。