下载文档原格式
第5讲 有向无环图应用之拓扑排序——教学讲义有向无环图（Directed Acyclic Graph ）是指一个无环的有向图，简称DAG 。
有向无环图可用来描述工程或系统的进行过程，如一个工程的施工图、学生课程间的制约关系图等。
拓扑排序用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（Activity On Vertex Network ），简称为AOV-网。
例如：计算机系学生的一些必修课程及其先修课程的关系如下：课程编号 课程名称 先修课程C 1 高等数学 无 C 2 程序设计基础 无 C 3离散数学 C 1,C 2 C 4 数据结构 C 2,C 3 C 5 算法语言 C 2 C 6 编译技术 C 4,C 5 C 7 操作系统 C 4,C 9 C 8 普通物理 C 1 C 9计算机原理C 8用顶点表示课程，弧表示先决条件，则上述关系可用一个有向无环图表示，见下图。
在有向图G=（V ，{E}）中， V 中顶点的线性序列（v i1,,v i1,,v i3,…，v in ）称为拓扑序列。
如果此序列满足条件：对序列中任意两个顶点v i 、v j ，在G 中有一条从v i 到v j 的路径，则在序列中v i 必排在v j 之前。
例如，上图的一个拓扑序列为： AOV-网的特性如下：若v i 为v j 的先行活动，v j 为v k 的先行活动，则v i 必为v k 的先行活动，即先C 1,C 2,C 3,C 4,C 5,C 8,C 9,C 7,C 6。
C 1 C 2C 3C 4C 5C 6 C 7 C 8 C 9表示课程之间优先关系的有向无环图行关系具有可传递性。
从离散数学的观点来看，若有<v i ,v j >、<v j ,v k >，则必存在<v j ,v k >。
显然，在AOV -网中不能存在回路，否则回路中的活动就会互为前驱，从而无法执行。
求拓扑序列排序课程设计一、教学目标本课程的教学目标是让学生掌握拓扑序列排序的基本概念、原理和应用，培养学生运用拓扑序列排序解决问题的能力。
具体包括以下三个方面的目标：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.实验设备：计算机、网络设备。
通过以上教学资源的使用，丰富学生的学习体验，提高学生的学习效果。
五、教学评估本课程的教学评估将采取多元化、全过程的方式进行，以全面、客观、公正地评价学生的学习成果。
拓扑排序一、拓扑排序就是按照给出的有向图对其进行排序：二、拓扑排序的思想（1）从AOV网中选择一个入度为0的顶点将其输出。
（2）在AOV网中删除此顶点及其所有的出边。
反复执行以上两步，直到所有顶点都已经输出为止，此时整个拓扑排序完成或者直到剩下的顶点的入度都不为0为止，此时说明AOV网中存在回路，拓扑排序无法再进行。
三、拓扑排序的算法拓扑排序前，先调用findInDegree得到所有结点的入度，然后将所有入度为0的顶点压栈。
从栈顶取出一个顶点将其输出，由它的出边表可以得到以该顶点为起点的出边，将这些边终点的入度减1，即删除这些边。
如果某条边终点的入度为0，则将该顶点入栈。
反复进行上述操作，直到栈为空。
如果这时输出的顶点个数小于n，则说明该AOV网中存在回路，否则，拓扑排序正常结束。
四、模板/*==================================================*\| 拓扑排序| INIT:edge[][]置为图的邻接矩阵;count[0…i…n-1]:顶点i的入度.\*==================================================*/void TopoOrder(int n){int i, top = -1;for( i=0; i < n; ++i )if( count[i] == 0 ){count[i] = top; top = i; // 下标模拟堆栈}for( i=0; i < n; ++i ) //表示要把n个点全部加入if( top == -1 ){printf("存在回路\n"); return ;}Else{int j = top; top = count[top]; //删除边进行更新printf("%d", j);for( int k=0; k < n; ++k )if( edge[j][k] && (--count[k]) == 0 ){count[k] = top; top = k;}}}五、省赛预选赛1005拓扑排序的修改#include<stdio.h>#include<stdlib.h>#include<string.h>int main(){int i,j;int n,m;int cin[110];int cout[110];int map[110][110];int num[110];int max[110];int a,b;int top;int flag;while(scanf("%d%d",&n,&m)!=EOF){for(i=1;i<=n;i++)scanf("%d",&num[i]);memset(map,0,sizeof(map));memset(cin,0,sizeof(cin));memset(cout,0,sizeof(cout));memset(max,0,sizeof(max));for(i=1;i<=m;i++){scanf("%d%d",&a,&b);if(map[a][b]==0){map[a][b]=num[a];cin[b]++;cout[a]++;}}top=-1;flag=1;for(i=1;i<=n;i++){if(cin[i]==0){cin[i]=top;top=i;}}for(i=1;i<=n;i++){if(top==-1){flag=0;break;}else{j=top;top=cin[top];for(int k=1;k<=n;k++){if(map[j][k]){if(max[j]+map[j][k]>max[k])//寻找一个有向图的最长的路径{max[k]=max[j]+map[j][k];}cin[k]--;if(cin[k]==0){cin[k]=top;top=k;}}}}}int ttt;ttt=0;if(flag==1){for(j=1;j<=n;j++){if(cout[j]==0){if(max[j]+num[j]>ttt)ttt=max[j]+num[j];}}printf("%d\n",ttt);}elseprintf("What a cup!\n");}}。
求拓扑排序序列课程设计一、教学目标本节课的教学目标是让学生掌握拓扑排序序列的概念、性质和求解方法，能够运用拓扑排序解决实际问题。
具体分为以下三个部分：1.知识目标：学生能够理解拓扑排序的定义，了解拓扑排序的性质和应用场景，掌握拓扑排序的求解方法。
2.技能目标：学生能够运用拓扑排序解决实际问题，如任务调度、项目规划等，提高问题解决的效率。
3.情感态度价值观目标：培养学生对计算机科学和图论的兴趣，培养学生的逻辑思维和创新能力。
二、教学内容本节课的教学内容主要包括以下三个方面：1.拓扑排序的定义和性质：介绍拓扑排序的定义，解释拓扑排序的性质，如无环性、唯一性等。
2.拓扑排序的求解方法：讲解拓扑排序的求解方法，如DFS、BFS等，并通过实例进行演示。
3.拓扑排序的应用：介绍拓扑排序在实际问题中的应用，如任务调度、项目规划等，并通过实例进行讲解。
三、教学方法为了提高学生的学习兴趣和主动性，本节课将采用以下教学方法：1.讲授法：讲解拓扑排序的定义、性质和求解方法，为学生提供系统的知识结构。
2.案例分析法：通过分析实际问题，让学生了解拓扑排序的应用，提高学生的解决问题的能力。
3.实验法：让学生动手实践，求解实际问题，培养学生的实际操作能力。
四、教学资源为了支持教学内容和教学方法的实施，丰富学生的学习体验，我们将准备以下教学资源：1.教材：为学生提供系统的知识结构，方便学生课后复习。
2.多媒体资料：通过动画、图片等形式，直观地展示拓扑排序的概念和性质，提高学生的学习兴趣。
3.实验设备：为学生提供实际操作的机会，培养学生的实际操作能力。
五、教学评估本节课的评估方式包括以下几个方面：1.平时表现：通过观察学生在课堂上的参与程度、提问回答等情况，评估学生的学习态度和理解程度。
2.作业：布置相关的拓扑排序题目，评估学生对拓扑排序概念和求解方法的理解和应用能力。
3.考试：设计考试题目，全面考察学生对拓扑排序的定义、性质、求解方法和应用的掌握程度。
课程设计拓扑排序摘要一、教学目标本课程的教学目标是使学生掌握拓扑排序的基本概念和方法，能够运用拓扑排序解决实际问题。
具体分为以下三个部分：1.知识目标：学生需要理解拓扑排序的定义、特点和应用场景，掌握拓扑排序算法的实现和优化。
2.技能目标：学生能够运用拓扑排序算法解决基本的图论问题，如任务调度、课程安排等。
3.情感态度价值观目标：通过学习拓扑排序，学生能够培养逻辑思维能力、问题解决能力和创新意识，提高对计算机科学和图论的兴趣。
二、教学内容本课程的教学内容主要包括拓扑排序的定义和性质、拓扑排序算法的实现和优化、拓扑排序的应用场景。
具体安排如下：1.第一章：拓扑排序的定义和性质，介绍拓扑排序的基本概念和特点，分析拓扑排序的性质和限制。
2.第二章：拓扑排序算法的实现和优化，讲解常见的拓扑排序算法，如Kahn算法和Dijkstra算法，探讨算法的效率和优化方法。
3.第三章：拓扑排序的应用场景，介绍拓扑排序在任务调度、课程安排等实际问题中的应用，并通过案例分析让学生掌握拓扑排序的运用。
三、教学方法为了激发学生的学习兴趣和主动性，本课程将采用多种教学方法相结合的方式进行教学。
具体包括：1.讲授法：通过讲解拓扑排序的基本概念、算法和应用，使学生掌握拓扑排序的理论基础。
2.案例分析法：通过分析实际问题案例，让学生了解拓扑排序在实际中的应用和解决问题的方式。
3.实验法：安排课后实验，让学生动手实现拓扑排序算法，培养学生的实际操作能力和问题解决能力。
四、教学资源为了支持教学内容和教学方法的实施，丰富学生的学习体验，我们将准备以下教学资源：1.教材：选择一本关于图论和拓扑排序的经典教材，作为学生学习的基础资料。
2.参考书：提供一些相关领域的参考书籍，供学生深入学习和拓展知识。
3.多媒体资料：制作PPT、教学视频等多媒体资料，帮助学生更好地理解和掌握拓扑排序的知识。
4.实验设备：准备计算机实验室，让学生能够进行课后实验和实践操作。
第八讲图（下）8.2 拓扑排序例：计算机专业排课课程号课程名称预修课程C1 程序设计基础无C2 离散数学无C3 数据结构C1, C2 C4 微积分（一）无C5 微积分（二）C4C6 线性代数C5C7 算法分析与设计C3C8 逻辑与计算机设计基础无C9 计算机组成C8C10 操作系统C7, C9 C11 编译原理C7, C9 C12 数据库C7C13 计算理论C2C14 计算机网络C10C15 数值分析C6C1C2C8C4C3C13C7C12C14C9C10C11C5C6C15 AOV(Activity On Vertex)网络拓扑排序⏹拓扑序：如果图中从V到W有一条有向路径，则V一定排在W之前。
满足此条件的顶点序列称为一个拓扑序⏹获得一个拓扑序的过程就是拓扑排序⏹AOV如果有合理的拓扑序，则必定是有向无环图（Directed Acyclic Graph, DAG）V V必须在V开始之前结束算法课程号课程名称预修课程C1 程序设计基础无C2 离散数学无C3 数据结构C1, C2 C4 微积分（一）无C5 微积分（二）C4C6 线性代数C5C7 算法分析与设计C3C8 逻辑与计算机设计基础无C9 计算机组成C8C10 操作系统C7, C9 C11 编译原理C7, C9 C12 数据库C7C13 计算理论C2C14 计算机网络C10C15 数值分析C6C1C13C2C3C12C14 C8C10C11C7C9C4C5C15C6C1C2C8C4C3C13C9C5C7C11C6C12C10C15C14算法void TopSort(){ for( cnt= 0; cnt< |V|; cnt++ ) {V = 未输出的入度为0的顶点;/* O(|V|) */if( 这样的V不存在) {Error ( “图中有回路”);break;}输出V，或者记录V的输出序号;for( V 的每个邻接点W)Indegree[W]––;}}T= O( |V|2)聪明的算法⏹随时将入度变为0的顶点放到一个容器里void TopSort(){ for( 图中每个顶点V )if( Indegree[V]==0 )Enqueue( V, Q );while( !IsEmpty(Q) ) {V = Dequeue( Q );输出V，或者记录V的输出序号; cnt++;for( V 的每个邻接点W )if( ––Indegree[W]==0 )Enqueue( W, Q );}if( cnt!= |V| )Error( “图中有回路”);} T= O( |V| + |E| )此算法可以用来检测有向图是否DAG关键路径问题⏹AOE (Activity On Edge)网络❑一般用于安排项目的工序v ja i 表示活动表示活动a i 到此结束持续时间C <i,j>机动时间D <i,j>顶点编号最早完成时间Earliest最晚完成时间Latest关键路径问题12345678开始结束64511297424问题1：整个工期有多长？064577Earliest[0] = 0;Earliest[j] = max { Earliest[i]+C <i,j>};<i,j>∈E161418Earliest[8] = 18问题2：哪几个组有机动时间？18161477Latest[8] = 18;Latest[i] = min { Latest[j]-C <i,j>};<i,j>∈E566D <i,j>= Latest[j]-Earliest[i]-C <i,j>223由绝对不允许延误的活动组成的路径。
拓扑排序一、问题描述在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)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。
拓扑排序c语言课程设计一、课程目标知识目标：1. 学生理解拓扑排序的概念，掌握其在图论中的应用。
2. 学生掌握使用C语言实现拓扑排序算法的基本步骤和关键代码。
3. 学生能够解释拓扑排序结果的意义，并分析其在实际问题中的应用。
技能目标：1. 学生能够运用C语言编写实现拓扑排序的程序，并对给定的有向无环图进行排序。
2. 学生通过实际操作，培养解决复杂问题的编程能力和逻辑思维能力。
3. 学生学会使用调试工具检测并修正程序中的错误，提高程序调试能力。
情感态度价值观目标：1. 学生在探究拓扑排序的过程中，培养对数据结构和算法的热爱，激发对计算机科学的兴趣。
2. 学生在合作交流中，培养团队协作精神和分享意识，提高沟通能力。
3. 学生通过解决实际问题，体会编程的魅力，增强自信心和自主学习能力。
课程性质：本课程为计算机科学与技术学科的课程设计，旨在让学生掌握拓扑排序的原理和C语言实现方法。
学生特点：学生已具备C语言基础，具有一定的编程能力和逻辑思维能力，对图论相关概念有一定了解。
教学要求：教师需引导学生通过实例分析，动手实践，掌握拓扑排序的编程方法，并在实际应用中提高解决问题的能力。
教学过程中注重培养学生的团队合作意识和自主学习能力。
通过本课程的学习，使学生在知识、技能和情感态度价值观方面取得具体的学习成果。
二、教学内容1. 图的基本概念复习：回顾图的定义、有向图和无向图、顶点和边、邻接矩阵和邻接表等基础知识。
教材章节：第二章 图的基本概念2. 拓扑排序的概念与性质：介绍拓扑排序的定义、特点和应用场景，讨论拓扑排序与有向无环图的关系。
教材章节：第五章 图的算法应用3. 拓扑排序算法原理：讲解拓扑排序的算法思想、关键步骤以及时间复杂度分析。
教材章节：第五章 图的算法应用4. C语言实现拓扑排序：详细讲解如何使用C语言实现拓扑排序，包括数据结构设计、函数定义和逻辑实现。
教材章节：实验指导书第四章 图的算法实现5. 拓扑排序实例分析：通过具体实例，分析拓扑排序在实际问题中的应用，如任务调度、项目规划等。
数据结构拓扑排序课程设计正文：1：引言1.1 研究背景在计算机科学领域中，数据结构是描述和组织数据的方式。
而拓扑排序是一种常用的数据结构算法，用于对有向图中的节点进行排序。
本文将介绍拓扑排序的算法原理以及如何实现一个拓扑排序算法。
1.2 研究目的本文的目的是设计一个高效的拓扑排序算法，用于解决日常生活中一些实际问题。
2：拓扑排序原理2.1 有向图有向图是由节点和边组成的图，边表示节点之间的关系，并且有方向性。
在有向图中，每个节点都有一个入度和一个出度。
2.2 拓扑排序定义拓扑排序是一种将有向无环图（DAG）中的节点线性排序的算法。
排序的结果满足：若节点 A 在排序结果中位于节点 B 之前，则在图中不存在一条从节点 B 指向节点 A 的路径。
2.3 拓扑排序算法步骤：1) 初始化一个队列，将所有入度为 0 的节点入队。
2) 当队列不为空时，执行以下操作：a) 取出队首节点，并将其加入排序结果中。
b) 将该节点的所有邻居节点的入度减 1：c) 若邻居节点的入度为 0，则将其入队。
3) 若排序结果中的节点数等于图中的节点数，则排序成功；否则，图中存在环，排序失败。
3：拓扑排序的实现3.1 数据结构设计为了实现拓扑排序算法，我们需要定义两个数据结构：节点和图。
节点类包含以下属性：- 节点标识符- 节点的入度- 节点的邻居列表图类包含以下方法：- 添加节点- 添加边- 拓扑排序3.2 代码实现示例代码如下：```pythonclass Node:def __init__(self, id): self：id = idself：indegree = 0 self：neighbors = [] class Graph:def __init__(self):self：nodes = []def addNode(self, id):self：nodes：append(Node(id)) def addEdge(self, id1, id2):node1 = self：getNode(id1)node2 = self：getNode(id2)node2：indegree += 1node1：neighbors：append(node2) def getNode(self, id):for node in self：nodes:if node：id == id:return nodereturn Nonedef topologicalSort(self):queue = []result = []for node in self：nodes:if node：indegree == 0:queue：append(node)while queue:currNode = queue：pop(0)result：append(currNode)for neighbor in currNode：neighbors: neighbor：indegree -= 1if neighbor：indegree == 0:queue：append(neighbor)if len(result) == len(self：nodes):return resultelse:return None```4：实例应用4.1 任务调度拓扑排序可以用于任务调度，其中每个节点表示一个任务，边表示任务之间的依赖关系。
课程设计实现拓扑排序算法一、课程目标知识目标：1. 学生能理解拓扑排序的概念，掌握拓扑排序算法的基本原理和应用场景。
2. 学生能描述有向无环图（DAG）的特点，并识别出给定图中的关键路径。
3. 学生能运用所学知识，对实际问题进行拓扑排序，解决项目管理、任务调度等实际问题。
技能目标：1. 学生能通过分析问题，构建出相应的有向无环图，并进行拓扑排序。
2. 学生能运用编程语言实现拓扑排序算法，解决具体问题。
3. 学生能通过实例分析，培养解决问题的能力和逻辑思维能力。
情感态度价值观目标：1. 学生通过学习拓扑排序算法，体验算法在实际问题中的应用价值，增强学习兴趣和动力。
2. 学生在团队协作中，培养沟通能力、合作精神和集体荣誉感。
3. 学生在学习过程中，树立正确的价值观，认识到科学技术的进步对社会发展的重要意义。
课程性质：本课程属于数据结构与算法领域，旨在帮助学生掌握拓扑排序这一重要算法，提高解决实际问题的能力。
学生特点：学生具备一定的编程基础和图论知识，具有一定的抽象思维和逻辑分析能力。
教学要求：结合学生特点和课程性质，教师应注重启发式教学，引导学生通过实例分析、编程实践等方式，掌握拓扑排序算法，提高实际应用能力。
同时，关注学生的情感态度价值观培养，激发学生的学习兴趣和动力。
在教学过程中，将课程目标分解为具体的学习成果，以便进行有效的教学设计和评估。
二、教学内容1. 图的基本概念复习：介绍图的相关术语，如顶点、边、邻接点、度等，回顾有向图和无向图的特点。
2. 有向无环图（DAG）的判定：讲解DAG的定义，引导学生识别DAG及其在实际问题中的应用。
3. 拓扑排序的概念与算法：介绍拓扑排序的定义，阐述拓扑排序的算法步骤，分析拓扑排序与DAG的关系。
4. 拓扑排序算法的实现：结合教材，教授编程语言实现拓扑排序算法，包括邻接表和邻接矩阵两种表示方法。
5. 拓扑排序的应用案例：分析拓扑排序在项目管理、任务调度等领域的应用，结合实际案例进行讲解。
拓扑排序在日常生活中，一项大的工程可以看作若干个子工程（这些子工程称为“活动”）组成的集合，这些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其他一些子工程完成之后才能开始，我们可以用有向图来形象的表示这些子工程之间的先后关系，子工程为顶点，子工程之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。
在AOV网中，有向边代表子工程的先后关系，即有向边的起点活动是终点活动的前驱活动，只有当起点活动完成之后终点活动才能进行。
如果有一条从顶点Vi到顶点Vj的路径，则说Vi是Vj的前驱，Vj是Vi的后继。
如果有弧<Vi,Vj>，则称Vi 是Vj的直接前驱，Vj是Vi的直接后继。
一个AOV网应该是一个有向无环图，即不应该带有回路，否则必定会有一些活动互相牵制，造成环中的活动都无法进行。
把不带回路的AOV网中的所有活动排成一个线性序列，使得每一个活动的所有前驱活动都排在该活动的前面，这个过程叫做拓扑排序。
所得到的活动序列称为拓扑序列。
需要注意的是AOV网的拓扑序列是不唯一的。
其实，构造拓扑序列的拓扑排序算法思想很简单：只要选择一个入度为0的顶点并输出，然后从AOV网中删除此顶点以及以此顶点为起点的所有关联边；重复上述两步，知道不存在入度为0的顶点为止，若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列。
为了算法实现上的方便，我们采用邻接表存储AOV网，不过稍作修改，在顶点表中增加一个记录顶点入度的域id，具体的拓扑排序算法描述如下：procedure topsort(dig:graphlist); {用邻接表dig存储图G}varn,top,i,j,k,m:integer;P:graphlist;beginn:=dig.adjv; {取顶点总个数}top:=0; {堆栈、初始化}for i:=1 to n do {对入度为0的所有顶点进行访问，序号压栈}if dig.adj[i].id=0 then begindig.adj[i].id:=top;top:=i;end;m:=0; {记录输出的顶点个数}while top<>0 do {栈不空}beginj:=top; {取一个入度为0的顶点序号}top:=dig.adj[top].id; {出栈、删除当前处理的顶点、指向下个入度为0的顶点} write(dig.adj[top].v); {输出顶点序号}inc(m);p：=dig.adj[j].link; {指向Vj邻接表的第一个邻接点}while p<>nil do {删除所有与Vj相关边}begink:=p^.adjv; {下一个邻接点}dig.adj[k].id:=dig.adj[k].id-1; {修正相应点的入度} if dig.adj[k].id=0 then begin {入度为0的顶点入栈}dig.adj[k].id:=top;top:=k;end;p:=p^.next; {沿边表找下一个邻接点}end;end;if m<n then writeln(‘no solution!’);{有回路}end.。
课题二拓扑排序2．1 问题的提出2.1 问题的提出任务：编写函数实现图的拓扑排序。
程序所实现的功能：建立对应的邻接表，对该图进行拓扑排序，并显示排序结果。
输入：顶点数, 边数及各顶点信息(数据格式为整形)输出：拓扑排序结果。
2. 2 概要设计1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。
更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。
拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。
2．解决拓扑排序的方法如下：（1）在有向图中选一个没有前驱的顶点且输出之。
（2）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。
后一种情况则说明有向图中存在环。
具体的算法实现参照源程序。
3．构造邻接表图：typedef struct{AdjList vertices;int vexnum,arcnum;}Graph;//邻接表图4.为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedef struct stack{int *base;int *top;int stacksize;}sqstack;//栈的结构，存储图的顶点序号2．3 流程图2.根据算法思想，画流程图如下：2．4 源代码//采用尾插法创的邻接图#include<iostream>using namespace std;const int MAX=20;const int STACK_INIT_SIZE=100;const int ERROR=0;typedef struct stack{int *base;int *top;int stacksize;}sqstack;//栈的结构，存储图的顶点序号typedef struct lnode{int adjvex;struct lnode *next;}ArcNode;//弧结点typedef struct node2{char data;ArcNode *fristarc;}VNode,AdjList[MAX];//顶点数组,fristarc指向与顶点邻接的第一条弧typedef struct{AdjList vertices;int vexnum,arcnum;}Graph;//邻接表图void Initstack(sqstack &s){s.base=new int;if(!s.base)exit(0);s.top=s.base;s.stacksize= STACK_INIT_SIZE;}void Push(sqstack &s,int &e){*s.top++=e;}int Emptystack(sqstack &s){if(s.base==s.top)return 1;elsereturn 0;}int Pop(sqstack &s,int &e){if(s.base==s.top)return ERROR;e=*--s.top;}void CreatGraph(Graph &G,int *indegree){cout<<"请输入图的顶点数和弧数(且顶点数不能超过"<<MAX<<")"<<endl; cin>>G.vexnum>>G.arcnum;cout<<"请输入顶点值:"<<endl;for(int i=0;i<G.vexnum;i++)//输入图的顶点{cin>>G.vertices[i].data;G.vertices[i].fristarc=NULL;indegree[i]=0;}for(i=0;i<G.arcnum;i++)//输入图的弧{int m,n;ArcNode *p;cout<<"请输入第"<<i+1<<"条弧的弧尾和弧头:"<<endl;cin>>m>>n;p=new ArcNode;if(!p)exit(0);indegree[n-1]++;//求每个顶点的入度值p->adjvex=n-1;p->next=G.vertices[m-1].fristarc;G.vertices[m-1].fristarc=p;}}int Toposort(Graph &G,int *indegree){sqstack S;Initstack(S);for(int i=0;i<G.vexnum;i++)//0入度顶点入栈{if(!indegree[i])Push(S,i);}int count=0;while(!Emptystack(S)){Pop(S,i);cout<<G.vertices[i].data<<" ";count++;//记录输出的顶点数for(ArcNode *p=G.vertices[i].fristarc;p;p=p->next)//把与顶点{ //相邻接的顶点的入度int k=p->adjvex;if(!(--indegree[k]))Push(S,k);}}if(count<G.vexnum)return 0;elsereturn 1;}int main(){Graph G;int *indegree;indegree=new int;CreatGraph(G,indegree);if(!Toposort(G,indegree)){cout<<endl;cout<<"拓扑排序不成功!"<<endl;}else{cout<<endl;cout<<"拓扑排序成功!"<<endl;}return 0;}2．5 结果与分析2.4 测试及性能分析1．它的时间复杂度是O(G.vexnum+G.arcnum)。
