下载文档原格式
拓扑排序序列的步骤拓扑排序是一种常用的有向图排序算法，它可以用来解决依赖关系的排序问题。
拓扑排序序列指的是通过拓扑排序算法得到的图中节点的一个线性排序。
在本文中，我们将深入探讨拓扑排序的步骤并给出实现示例。
一、拓扑排序简介拓扑排序适用于有向无环图（DAG）。
它的基本思想是将有向图中的节点按照依赖关系排序，使得每个节点的所有前驱节点都在它的前面。
如果存在环路，则无法进行拓扑排序。
二、拓扑排序步骤1. 初始化一个队列，用于储存入度为0的节点。
2. 遍历图中的所有节点，并统计每个节点的入度，将入度为0的节点加入队列。
3. 从队列中取出一个节点，将其输出，并将其所有邻接节点的入度减1。
4. 如果邻接节点的入度变为0，则将其加入队列。
5. 重复步骤3和步骤4，直到队列为空。
6. 如果输出的节点数量与图中节点的数量相同，则拓扑排序成功；否则，说明图中存在环路，无法进行拓扑排序。
示例代码如下：```pythondef topological_sort(graph):indegree = [0] * len(graph)queue = []# 统计每个节点的入度for node in graph:for adjacent in graph[node]: indegree[adjacent] += 1 # 将入度为0的节点加入队列 for i in range(len(indegree)):if indegree[i] == 0:queue.append(i)result = []while queue:node = queue.pop(0)result.append(node)# 将邻接节点的入度减1 for adjacent in graph[node]:indegree[adjacent] -= 1if indegree[adjacent] == 0: queue.append(adjacent) # 判断是否成功拓扑排序if len(result) == len(graph):return resultelse:return []# 图的邻接表表示graph = {0: [1, 2],1: [3, 4],2: [3],3: [],4: [3]}result = topological_sort(graph)if result:print("拓扑排序序列为:", result)else:print("图中存在环路，无法进行拓扑排序")```以上代码实现了拓扑排序的步骤，可以根据具体需求进行调用和扩展。
数据结构的应用的拓扑排序与关键路径算法拓扑排序与关键路径算法是数据结构中重要的应用之一。
拓扑排序通过对有向图的节点进行排序，使得对于任意一条有向边(u,v)，节点 u 在排序中都出现在节点 v 之前。
关键路径算法则是用来确定一个项目的关键活动和最短完成时间。
拓扑排序的实现可以通过深度优先搜索或者广度优先搜索来完成。
深度优先搜索是递归地访问节点的所有未访问过的邻居节点，直到没有未访问过的邻居节点为止，然后将该节点添加到拓扑排序的结果中。
广度优先搜索则是通过使用队列来实现的，将节点的邻居节点逐个入队并进行访问，直到队列为空为止。
无论使用哪种方法，拓扑排序都可以通过判断节点的入度来进行。
拓扑排序在很多实际问题中都有广泛应用。
比如在任务调度中，拓扑排序可以用来确定任务间的依赖关系和执行顺序；在编译原理中，拓扑排序可以用来确定程序中变量的定义和使用顺序。
关键路径算法用于确定项目中的关键活动和最短完成时间。
它通过计算每个活动的最早开始时间和最晚开始时间，以及每个活动的最早完成时间和最晚完成时间来实现。
具体步骤如下：1. 构建有向加权图，其中节点表示项目的活动，有向边表示活动间的先后关系，边的权重表示活动的持续时间。
2. 进行拓扑排序，确定活动的执行顺序。
3. 计算每个活动的最早开始时间，即从起始节点到该节点的最长路径。
4. 计算每个活动的最晚开始时间，即从终止节点到该节点的最长路径。
5. 根据每个活动的最早开始时间和最晚开始时间，可以确定关键活动，即最早开始时间与最晚开始时间相等的活动。
6. 计算整个项目的最短完成时间，即从起始节点到终止节点的最长路径。
拓扑排序与关键路径算法在工程管理、任务调度、生产流程优化等领域都有重要应用。
它们能够帮助我们有效地组织和管理复杂的项目，提高工作效率和资源利用率。
在实际应用中，我们可以借助计算机编程以及各种图算法库来实现这些算法，从而更快速、准确地解决实际问题。
综上所述，拓扑排序与关键路径算法是数据结构的重要应用之一。
图的拓扑排序算法图是计算机科学中常用的数据结构之一，它由一些节点（点）和连接这些节点的边（线）组成。
在计算机科学中，图经常被用来解决很多问题，例如计算机网络路由、调度、自然语言处理等等。
其中，图的拓扑排序算法是一个十分重要且广泛应用的算法。
在本文中，我们将详细介绍图的拓扑排序算法的原理及应用。
一、拓扑排序算法简介首先，我们来了解一下什么是拓扑排序算法。
拓扑排序是指将有向无环图(Directed Acyclic Graph, DAG)中节点按照拓扑序列排列的过程。
拓扑序列是指，在排列中，如果存在一条从节点A到节点B的路径，那么在拓扑序列中节点A必须出现在节点B之前。
如果存在环路，则不存在拓扑序列。
拓扑排序算法通常用于任务调度等场景中。
在计算机科学中，拓扑排序算法可以使用两种方法进行实现：基于搜索的算法和基于入度的算法。
二、基于搜索的算法基于搜索的算法是一种比较直接的实现思路，我们可以使用深度优先搜索或者广度优先搜索来实现。
深度优先搜索的方法是，先访问图中入度为0的节点，将其加入拓扑序列中，并将其后继节点的入度减1，直到遍历完整幅图。
基于入度的算法基于入度的算法是另一种有用的实现思路。
首先，我们可以记录每个节点的入度值。
入度是指图中所有指向该节点的边的个数。
对于一个拓扑序列中的节点，它的入度必定为0。
因此，我们可以将入度为0的节点放入队列中，然后对该节点的后继节点的入度减1。
如果减去入度后某个节点的入度为0，则也将其加入队列中。
不断循环这一过程，直到遍历完整幅图。
三、应用场景拓扑排序算法可以在很多场景中应用。
例如，任务调度。
在计算机中，任务调度是指将一些任务分配给不同的处理器进行处理的过程。
我们可以将每个任务看作一个节点，处理器看作边。
拓扑排序算法可以帮助我们找到一个最优的任务调度方案。
另一个应用场景是编译器和依赖管理器。
在编译一个程序时，我们需要按指定顺序编译不同的模块。
如果模块之间存在依赖关系，则需要使用拓扑排序算法来进行模块的编译顺序优化。
数据结构之的拓扑排序算法拓扑排序算法的实现和性能分析数据结构之拓扑排序算法拓扑排序算法的实现和性能分析拓扑排序是一种常用的图算法，用于对有向无环图（DAG）进行排序。
拓扑排序的主要应用包括任务调度、编译顺序、依赖关系管理等方面。
本文将介绍拓扑排序算法的实现及其性能分析。
一、拓扑排序算法的实现拓扑排序算法一般采用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。
下面将以DFS实现为例进行介绍。
1. 创建图数据结构在进行拓扑排序之前，首先需要创建图的数据结构。
可以使用邻接表或邻接矩阵来表示图。
以邻接表为例，可以使用一个字典来表示每个节点和其相邻节点的关系。
2. 初始化标记数组为了保证每个节点只被访问一次，需要使用一个标记数组来记录节点的访问状态。
可以使用布尔数组或整数数组来表示，将未访问的节点标记为false或0，已访问的节点标记为true或1。
3. 实现拓扑排序函数拓扑排序函数的主要功能是对图进行遍历，并将节点按照拓扑排序的顺序输出。
拓扑排序函数通常使用递归的方式实现。
4. 输出排序结果拓扑排序算法完成后，可以将排序的结果输出。
按照拓扑排序的定义，输出的结果应该是一个拓扑有序的节点列表。
二、拓扑排序算法的性能分析拓扑排序算法的性能取决于图的规模和结构。
下面将从时间复杂度和空间复杂度两个方面进行性能分析。
1. 时间复杂度分析拓扑排序算法的时间复杂度主要取决于图的节点数和边数。
在最坏情况下，每个节点都需要遍历一次，而每个节点的边数是有限的，所以拓扑排序的时间复杂度为O(V+E)，其中V表示节点数，E表示边数。
2. 空间复杂度分析拓扑排序算法的空间复杂度主要取决于存储图和标记数组的空间。
在使用邻接表表示图时，需要额外的空间来存储每个节点及其相邻节点的关系。
同时，需要使用标记数组来记录节点的访问状态。
所以拓扑排序的空间复杂度为O(V+E+V)，即O(V+E)，其中V表示节点数，E表示边数。
三、总结拓扑排序是一种常用的图算法，可以对有向无环图进行排序。
数据结构之拓扑排序算法详解拓扑排序算法是一种常用于有向无环图（DAG）的排序算法，它可以将图中的顶点按照一定的顺序进行排序，使得图中任意一条有向边的起点在排序结果中都排在终点的前面。
在实际应用中，拓扑排序算法常用于解决任务调度、依赖关系分析等问题。
本文将详细介绍拓扑排序算法的原理、实现方法以及应用场景。
### 一、拓扑排序算法原理拓扑排序算法的原理比较简单，主要包括以下几个步骤：1. 从DAG图中选择一个入度为0的顶点并输出。
2. 从图中删除该顶点以及以该顶点为起点的所有有向边。
3. 重复步骤1和步骤2，直到图中所有顶点都被输出。
### 二、拓扑排序算法实现下面以Python语言为例，给出拓扑排序算法的实现代码：```pythondef topological_sort(graph):in_degree = {v: 0 for v in graph}for u in graph:for v in graph[u]:in_degree[v] += 1queue = [v for v in graph if in_degree[v] == 0] result = []while queue:u = queue.pop(0)result.append(u)for v in graph[u]:in_degree[v] -= 1if in_degree[v] == 0:queue.append(v)if len(result) == len(graph):return resultelse:return []# 测试代码graph = {'A': ['B', 'C'],'B': ['D'],'C': ['D'],'D': []}print(topological_sort(graph))```### 三、拓扑排序算法应用场景拓扑排序算法在实际应用中有着广泛的应用场景，其中包括但不限于以下几个方面：1. 任务调度：在一个任务依赖关系图中，拓扑排序可以确定任务的执行顺序，保证所有任务按照依赖关系正确执行。
数据结构拓扑排序实验报告正文：一、实验目的本实验旨在通过实现拓扑排序算法来加深对数据结构中图的相关概念的理解，掌握拓扑排序的具体步骤与实现方法。
二、实验原理拓扑排序是一种对有向无环图进行排序的算法，它可以将有向无环图的顶点按照线性的顺序排列出来，使得对于任何一个有向边(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. 结果分析可以看出，根据有向图的依赖关系，拓扑排序算法能够将顶点按照合理的顺序进行排序。
拓扑排序的结果可以作为图中顶点的执行顺序，具有重要的应用价值。
五、实验总结通过本次实验，我们深入学习了拓扑排序算法，并成功实现了拓扑排序的过程。
拓扑排序在图论和数据结构中具有广泛的应用，对于理解和解决与图相关的问题具有重要意义。
六、附件本文档没有涉及附件内容。
七、法律名词及注释本文档没有涉及法律名词及注释。
拓扑数据结构的名词解释随着科技的快速发展，数据的规模和复杂度急剧增加，大数据和人工智能成为了当今世界的热点话题。
在处理如此庞大和复杂的数据时，拓扑数据结构扮演着重要的角色。
本文将对拓扑数据结构的相关术语进行解释，帮助读者更好地理解这一概念。
一、图 (Graph)图是拓扑数据结构的基础。
它由节点集合和边集合组成。
节点代表实体，边则表示节点之间的关系。
图可以用来描述各种各样的关系网络，如社交网络、交通网络等。
图可以分为有向图和无向图，有向图的边是有方向的，而无向图的边是无方向的。
二、节点 (Node)节点是图的基本元素，也称为顶点。
每个节点可以具有零个或多个关联的边，用来表示节点之间的关系。
节点可以包含数据、属性和其他相关信息。
三、边 (Edge)边是图中节点之间的连接线。
边可以是有向的，表示从一个节点到另一个节点的单向关系；也可以是无向的，表示两个节点之间的双向关系。
边可以具有权重，用来表示节点之间的关联强度或距离。
四、路径 (Path)路径是图中的一条连接序列，由一系列的边组成。
路径可以是闭合的，即起点和终点相同，形成环；也可以是非闭合的，连接不同的节点。
五、连通性 (Connectivity)连通性是指图中节点之间的关联程度。
一个图可以是强连通的，即任意两个节点之间都存在路径；也可以是弱连通的，即只有部分节点之间存在路径。
六、拓扑排序 (Topological Sorting)拓扑排序是对有向无环图进行排序的一种算法。
在一个有向图中，如果存在一条路径从节点 A 到节点 B，那么在排序结果中，节点 A 应该在节点 B 的前面。
拓扑排序可以用来解决任务调度、依赖关系等问题。
七、最短路径 (Shortest Path)最短路径是指在图中找到两个节点之间路径长度最短的路径。
最短路径算法可以用来解决如最优路径规划、网络路由等问题。
常见的最短路径算法包括迪杰斯特拉算法和弗洛伊德算法。
八、网络流 (Network Flow)网络流是指在图中沿着边进行的一种资源分配。
拓扑排序讲解+例题对⼀个==有向⽆环图(Directed Acyclic Graph简称DAG)==G进⾏拓扑排序，是将G中所有顶点排成⼀个线性序列，使得图中任意⼀对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。
通常，这样的线性序列称为满⾜拓扑次序(Topological Order)的序列，简称拓扑序列。
简单的说，由某个集合上的⼀个偏序得到该集合上的⼀个全序，这个操作称之为拓扑排序。
⽐如说给定若⼲个两个元素之间的⼤⼩关系，要转换成所有元素的总体⼤⼩关系，就可以⽤拓扑排序来处理下⾯给出的例题就是这个样⼦关于拓扑排序还有⼀种⽤法->判断给定的有向图中是否存在环下⾯来说明⼀下拓扑排序的相关步骤：（默认已经将图存好）⾸先统计所有点的⼊度，然后将所有点⼊度为0的所有点放进队列（根据题⽬特殊要求也可以使⽤优先队列）然后采取像BFS那样的⽅式，当队列⾮空的时候，始终取队列头端的⼀个元素，并将这个元素记录下来之后pop掉，把这个点（⽐如说是点P）放进⽤来存储拓扑序列的不定长数组vector中，然后遍历和这个点相连的所有点，并将与点P相连的所有点的⼊度减少1（换句话说讲点P去掉之后，他的指向关系就会消失，并且以他为起点的所有点的⼊度都会减⼩1），如果这个点的⼊度刚好为0，那么正好可以将这个点继续放到队列中，如此反复伪代码如下void top_sort(){for(int i=1;i<=n;i++){if(⼊读为0) que.push(i);}while(que.size()){int top = que.top()/que.front();que.pop();vet.push_back(这个点->top);for(int i=1;i<=n;i++){///在数据范围⾜够⼩的情况下可以直接采取⼆维数组存图/// gra[i][j] == 1表⽰有⼀条从i指向j的边，反之没有if(相连){deg[i]--;if(deg[i] == 0) que.push(i);}}}}下⾯是⽐较常⽤的⼩模板：priority_queue <int, vector<int>, greater<int> >litt;int dege[507];int n,m;int gra[507][507];vector<int>vet;void top_sort(){for(int i=1;i<=n;i++){if(dege[i] == 0) litt.push(i);}while(litt.size()){int tp = litt.top();litt.pop();vet.push_back(tp);for(int i=1;i<=n;i++){if(gra[tp][i]){dege[i] --;if(dege[i] == 0) litt.push(i);}}}}下⾯来看例题：题⽬描述有N个⽐赛队（1<=N<=500），编号依次为1，2，3，。
拓扑排序算法解法1. 什么是拓扑排序算法拓扑排序是一种用于有向无环图（DAG）的排序算法，它将图中的节点按照一定的顺序进行排序。
拓扑排序算法可以用来解决一些依赖关系的问题，比如任务调度、编译顺序等。
2. 拓扑排序的应用场景拓扑排序算法在实际应用中有很多用途，下面列举几个常见的应用场景： 1. 任务调度：在一个任务依赖关系的系统中，拓扑排序可以确定任务的执行顺序，保证每个任务在其依赖的任务完成后才能执行。
2. 项目管理：在一个项目中，任务之间可能存在依赖关系，拓扑排序可以帮助确定任务的执行顺序，确保项目能够按照预定计划进行。
3. 课程安排：在一个学期中，课程之间可能存在依赖关系，拓扑排序可以帮助学校确定课程的安排顺序，保证学生按照正确的顺序学习课程。
3. 拓扑排序算法的实现原理拓扑排序算法的实现原理主要包括以下几个步骤： 1. 构建图：首先需要将问题转化为一个有向无环图（DAG），图中的每个节点表示一个任务或者一个对象，有向边表示任务之间的依赖关系。
2. 计算入度：对于图中的每个节点，需要计算其入度，即有多少个节点指向该节点。
3. 初始化队列：将入度为0的节点加入一个队列中。
4. 遍历队列：从队列中取出一个节点，将其加入结果列表，并将其指向的节点的入度减1。
如果入度减为0，则将该节点加入队列中。
5. 判断是否存在环：如果结果列表的长度等于图中的节点数，则说明不存在环，算法结束。
如果结果列表的长度小于节点数，则说明存在环，算法结束。
4. 拓扑排序算法的实现步骤下面是拓扑排序算法的具体实现步骤：4.1 构建图首先需要将问题转化为一个有向无环图（DAG）。
可以使用邻接表或者邻接矩阵来表示图。
4.2 计算入度对于图中的每个节点，需要计算其入度，即有多少个节点指向该节点。
可以使用一个数组来保存每个节点的入度。
4.3 初始化队列将入度为0的节点加入一个队列中。
4.4 遍历队列从队列中取出一个节点，将其加入结果列表，并将其指向的节点的入度减1。
拓扑排序简单的例子拓扑排序是一种对有向无环图(Directed Acyclic Graph, DAG)进行排序的方法，它可以帮助我们确定图中所有节点的线性顺序。
拓扑排序在实际应用中非常有用，例如任务调度、编译顺序等场景。
下面将从不同的角度给出10个简单的拓扑排序的例子，以展示其用途和特点。
标题1：拓扑排序概述拓扑排序是一种对有向无环图进行排序的方法，它可以帮助我们确定图中所有节点的线性顺序。
拓扑排序的基本原理是通过不断删除入度为0的节点，直到所有节点都被删除或没有入度为0的节点为止。
拓扑排序可以应用于各种实际场景，例如任务调度、编译顺序等。
标题2：任务调度的拓扑排序在任务调度中，我们需要确定任务的执行顺序，以保证所有任务都能按照正确的顺序运行。
拓扑排序可以帮助我们解决这个问题。
例如，假设有一组任务，它们之间存在依赖关系，我们可以使用拓扑排序确定它们的执行顺序，从而保证任务能够按照正确的顺序完成。
标题3：编译顺序的拓扑排序在编译过程中，我们需要确定源代码文件的编译顺序，以保证所有文件都能正确地被编译。
拓扑排序可以帮助我们解决这个问题。
例如，假设有一组源代码文件，它们之间存在依赖关系，我们可以使用拓扑排序确定它们的编译顺序，从而保证文件能够按照正确的顺序被编译。
标题4：拓扑排序的应用举例除了任务调度和编译顺序外，拓扑排序还可以应用于其他许多场景。
例如，在学校的课程安排中，拓扑排序可以帮助我们确定课程的学习顺序。
在软件工程中，拓扑排序可以用于解决模块的依赖关系。
在交通规划中，拓扑排序可以用于确定道路的修建顺序。
总之，拓扑排序在各个领域都有重要的应用。
标题5：拓扑排序的算法步骤拓扑排序的算法步骤如下：1. 找到图中入度为0的节点，将其加入结果集中。
2. 删除该节点以及与其相连的边。
3. 重复步骤1和步骤2，直到所有节点都被删除。
4. 如果还有剩余的节点没有被删除，则说明图中存在环，无法进行拓扑排序。
标题6：用邻接表表示图在拓扑排序中，我们通常使用邻接表来表示图。
图的拓扑排序图的拓扑排序（TopologicalSorting）是指将一个有向无回路的图的顶点排序的方法。
它的表示和排序经常是一个有向图的核心。
有许多应用，用拓扑排序实现，比如活动安排问题、调度问题等，也能应用在计算机科学中，比如求解依赖关系等。
图的拓扑排序实际上是个结构优化问题，要求以最少的顶点构成图，使得它能够完整描述一个有向无回路图。
“拓扑排序”这个名称源自拓扑学，它是一种研究许多结构的学科，主要是用来描述无自循环的有向图的结构特性。
拓扑排序则是根据拓扑学来对给定的图进行排序，以使其有序化。
拓扑排序的基本原理是从一个有向图开始，把它分解成多个有向图的子图，而每个子图只有一个顶点没有出度。
从其中一个没有出度的顶点开始，把它加入到一个结果序列，接着从它的邻节点中选择一个没有出度的顶点，加入到结果序列中，直到所有顶点加入到结果序列中，就得到了一个有序的拓扑排序结果。
在有向图的拓扑排序中，有若干种算法，如拓扑排序算法、Kahn 算法、深度优先搜索算法等，它们经常用来在有向图中完成拓扑排序。
拓扑排序算法要求每个节点拥有一个入度（可以理解为前驱节点的个数），会用入度为0的节点来构成起点，然后按照节点的入度从小到大的顺序搜索，直到所有节点都被搜索。
Kahn算法与拓扑排序算法类似，它使用一个队列，从0入度的节点开始，把所有的0入度的节点入队，然后按照它们的出度，从队列里取出每一个节点，把节点的所有后继节点减1入度，如果减完之后发现有入度为0的节点，那么就入队，直到队列为空，就可以完成拓扑排序。
深度优先搜索算法也可以用来进行拓扑排序，它的基本思想是，从一个节点开始，按照深度优先搜索的方式，把节点进行拓扑排序，直到所有节点都被搜索完毕，就可以得到一个拓扑排序的序列。
在实际应用中，拓扑排序经常被用来解决活动安排问题和调度问题，因为这些问题都可以抽象成图模型来表示，而图的拓扑排序可以由此得到一个有序的序列，使得它们能够在正确的时序内完成。
成绩14信计 2015-2016（一）数据结构课程设计设计题目拓扑排序设计时间——学生姓名冯佳君学生学号20140401105所在班级14信计 1指导教师刘风华徐州工程学院数学与物理科学学院一、需求剖析1.问题描绘本次课程设计题目是：用毗邻表结构图而后进行拓扑排序，输出拓扑排序序列。
拓扑排序的基本思想为：1)从有向图中选一个无前驱的极点输出；2)将此极点和以它为起点的弧删除；3)重复 1) 、 2) 直到不存在无前驱的极点；4)若此时输出的极点数小于有向图中的极点数，则说明有向图中存在回路，不然输出的极点的次序即为一个拓扑序列。
2.拓扑排序有向图拓朴排序算法的基本步骤以下：1 ）从图中选择一个入度为0 的极点，输出该极点；2 ）从图中删除该极点及其有关系的弧，调整被删弧的弧头结点的入度（入度-1 ）；3）重复履行 1）、 2）直到全部极点均被输出，拓朴排序达成或许图中再也没有入度为 0 的极点（此种状况说明原有向图含有环）。
3．基本要求(1)输入的形式和输入值的范围；第一是输入要排序的极点数和弧数，都为整型，中间用分开符分开；再输入各极点的值，为正型，中间用分开符分开；而后输入各条弧的两个极点值，先输入弧头，再输入弧尾，中间用分开符分开，输入的值只好是开始输入的极点值不然系统会提示输入的值的极点值不正确，请从头输入，只需持续输入正确的值就行。
(2)输出的形式；第一输出成立的毗邻表，而后是最后各极点的出度数，再是拓扑排序的序列，而且每输出一个极点，就会输出一次各极点的入度数。
(3)程序所能达到的功能；因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用极点表示活动，有向边就表示活动间先后次序，那么输出的拓扑序列就表示各极点间的关系为反应出各点的储存结构，以毗邻表储存并输出各极点的入度。
二、纲要设计1.算法顶用到的全部各样数据种类的定义在该程序顶用毗邻表作为图的储存结构。
. . .. . .课程设计任务书学生：专业班级：指导教师：工作单位：计算机科学系题目: 拓扑排序初始条件：（1）采用邻接表作为有向图的存储结构；（2）给出所有可能的拓扑序列。
（3）测试用例见严蔚敏《数据结构习题集(C语言版)》p48题7.9图要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下容：1. 问题描述简述题目要解决的问题是什么。
2. 设计存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。
4. 经验和体会（包括对算法改进的设想）5. 附源程序清单和运行结果。
源程序要加注释。
如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。
说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。
2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。
时间安排：1．第17周完成，验收时间由指导教师指定2．验收地点：实验中心3．验收容：可执行程序与源代码、课程设计报告书。
指导教师签名：2013年6月14日系主任（或责任教师）签名：年月日拓扑排序目录1问题描述2具体设计2.1存储结构设计2.2主要算法设计2.2.1拓扑排序的算法总体设计2.2.2将有向图表示为邻接表2.2.3拓扑排序函数的设计2.2.4顺序表的运算设计2.3测试用例设计3调试报告3.1设计和编码的分析3.2调试过程问题及解决4经验与体会5用户使用说明6参考文献7附录源代码与运行结果1问题描述题目：拓扑排序如果用有向图表示一个工程，在这种有向图中，用顶点表示活动，用有向边<vi,vj>表示活动vi必须先于活动vj进行，这种有向图叫做顶点表示活动的网络，记作AOV 网络。
对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得AOV网络中的所有应存在前驱和后继的关系都能得到满足，这种构造AOV网络全部顶点的拓扑有序序列的运算叫做拓扑排序。
14信计2015-2016（一）数据结构课程设计设计题目拓扑排序设计时间2016.1.11——2016.1.15学生姓名冯佳君学生学号20140401105所在班级14信计1指导教师刘风华徐州工程学院数学与物理科学学院一、需求分析1.问题描述本次课程设计题目是：用邻接表构造图然后进行拓扑排序，输出拓扑排序序列。
拓扑排序的基本思想为：1)从有向图中选一个无前驱的顶点输出；2)将此顶点和以它为起点的弧删除；3) 重复1)、 2)直到不存在无前驱的顶点；4) 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。
2.拓扑排序有向图拓朴排序算法的基本步骤如下：1）从图中选择一个入度为0的顶点，输出该顶点；2）从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度-1）；3）重复执行1）、2）直到所有顶点均被输出，拓朴排序完成或者图中再也没有入度为0的顶点（此种情况说明原有向图含有环）。
3．基本要求(1)输入的形式和输入值的范围；首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。
(2)输出的形式；首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。
(3) 程序所能达到的功能；因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。
二、概要设计1. 算法中用到的所有各种数据类型的定义在该程序中用邻接表作为图的存储结构。
首先，定义表结点和头结点的结构类型，然后定义图的结构类型。
创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。
拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。
2.各程序模块之间的层次调用关系第一部分，void ALGraph *G函数构建图，用邻接表存储。
这个函数没有调用函数。
第二部分，void TopologicalSort(ALGraph *G)输出拓扑排序函数，这个函数首先调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1];然后设置了一个辅助栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不为空时，调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegree[k]--,当输出某一入度为0的顶点时，便将它从栈中删除。
第三部分，主函数，先后调用void CreatGraph(ALGraph *G)函数构建图、void TopologicalSort(ALGraph *G)函数输出拓扑排序实现整个程序。
3.设计的主程序流程(见附页)流程图：：三、详细设计（实现概要设计中定义的所有数据类型,对每个操作写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为；按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);写出出函数和过程的调用关系。
）1.实现概要设计中定义的所有数据类型#include<stdio.h>#include<stdlib.h>#define MAX_VEXTEX_NUM 100#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define M 100#define ERROR 0typedef int ElemType;typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;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;2.算法和各模块的代码程序中各函数算法思想如下：2.1 void InitStack(SqStack *S)初始化栈将栈的空间设为 STACK-INIT-SIZE。
2.2 int Pop(SqStack *S,ElemType *e)出栈操作，若站不空，删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。
2.3 void Push(SqStack *S,ElemType e)进栈操作，插入元素e为新的栈顶元素。
2.4 int StackEmpty(SqStack *S)判断栈是否为空,语句if (S->top=S->base )判断，若栈不为空，则删除S 的栈顶元素，并返回OK；否则返回ERROR。
2.5 void CreatGraph (ALGraph *G)构建图，用邻接表存储，首先定义邻接表指针变量，输入顶点数和弧数，初始化邻接表，将表头向量域置空，输入存在弧的点集合，当输入顶点值超出输入值的范围就会出错，否则依次插入进邻接表，最后输出建立好的邻接表。
2.6 void FindInDegree(ALGrap G, int indegreee[])求入度操作，设一个存放各顶点入度的数组indegreee[]，然后indegreee[i]=0赋初值，for循环indegreee[]++，存储入度数。
2.7 void TopologicalISort(ALGraph G)输出拓扑排序函数。
其思路是若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR。
首先由于邻接表的存储结构入度为零的顶点即为没有前驱的顶点，我们可以附设一个存放个顶点入度的数组，调用FindInDegree( G, indegreee[])对各顶点求入度；为了避免重复检测入度为零0的顶点，设置一个栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不为空时，调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegree[k]--,当输出某一入度为0的顶点时，便将它从栈中删除。
3.算法的时间复杂度和空间复杂度拓扑排序实际是对邻接表表示的图G进行遍历的过程，每次访问一个入度为零的顶点，若图G中没有回路，则需扫描邻接表中的所有边结点，在算法开始时，为建立入度数组D需访问表头向量中的所有边结点，算法的时间复杂度为O(n+e)。
四、测试与分析输入：结果如下：五、总结拓扑排序就是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。
在进行课程设计中，更好的认识了拓扑排序。
理清了各个模块之间算法之间的条理。
认识了伪代码（Pseudocode）是一种算法描述语言。
使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。
因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。
介于自然语言与编程语言之间。
它是一种让人便于理解的代码。
不依赖于语言的，用来表示程序执行过程，而不一定能编译运行的代码。
在数据结构讲算法的时候用的很多。
在设计中，我们遇到了程序正确，却对某些无向图无法进行拓扑排序的问题。
多次对程序进行修改后，才可以进行拓扑排序。
问题出在调用函数的错误理解，模块之间的联系模糊不清。
附录：源程序：#include<stdio.h>#include<stdlib.h>#define MAX_VEXTEX_NUM 100#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define M 100#define ERROR 0typedef int ElemType;typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;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 *);int Pop(SqStack *, ElemType *);void Push(SqStack *,ElemType );int StackEmpty(SqStack *);void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int * );void TopologicalSort(ALGraph );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;}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 = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType)); 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;elsereturn ERROR;}void CreatGraph(ALGraph *G){int m, n, i;ArcNode *p;printf("请输入顶点数和边数:");scanf("%d%d",&G->vexnum,&G->arcnum);for (i = 1; i <= G->vexnum; i++){G->vertices[i].data = i;G->vertices[i].firstarc = NULL;}for (i = 1; i <= G->arcnum; i++){printf("\n请输入存在边的两个顶点的序号，先输入弧尾，再输入弧头:"); scanf("%d%d",&n,&m);while (n < 0 || n > G->vexnum || m < 0 || 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;}}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){int indegree[M];int i, k, n,b,j=0;int a[20];int count = 0;ArcNode *p;SqStack S;FindInDegree(G, indegree);InitStack(&S);for ( i = 1; i <= G.vexnum; i++){if (!indegree[i])Push(&S,i);}while(!StackEmpty(&S)){Pop(&S,&n);a[j]=G.vertices[n].data;j++;count++;for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc) {k = p->adjvex;if (!(--indegree[k])){Push(&S,k);}}}printf("\n");if (count < G.vexnum){printf("该有向图有环\n");}else{printf("排序成功\n");printf("进行拓扑排序输出顺序为:"); for (b=0;b<j;b++){printf("%4d",a[b]);}printf("\n");}}int main(void){ALGraph G;CreatGraph(&G);TopologicalSort(G);system("pause");return 0;}。
