数据结构学年论文.doc

目录摘要.1关键词.1前言.21.拓扑排序的定义.3 2.图的邻接表表示.4 2.1邻接表的定义.4 2.2邻接表的存储方式.5 2.3用邻接表构造有向图.6 2.4有向图中顶点的入度.6 3.拓扑排序.7 3.1拓扑排序的方法.7 3.2举例说明.7 4.在计算机中实现拓扑排序.8 5.参考文献.10拓扑排序摘要：在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在有向图中若以顶点表示活动，有向边表示活动之间的先后关系，这样的图简称为AOV网。在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。关键词：拓扑排序、拓扑有序Abstract: in modern management, people commonly used directed graph to describe and analysis of a project plan and implementation process, a project are often divided into a number of small son engineering, the child project called activities (Activity), in the directed graph with vertices if said activities, directed edge between the said activities have relations, so chart referred to as AOV net. In the AOV net in order to better perform engineering, must meet between activities have relations, need to each activity row a sequence that is for topological sort. Keywords: topological sort, topology and orderly 1前言： 什么是拓扑排序？从离散数学的角度来看，拓扑排序就是由某集合上的一个偏序得到该集合上的一个全序。直观的来说，偏序即集合中仅部分元素间可比较（存在某些元素间无法比较），全序即集合中所有元素间均可比较。 更直观地，一个偏序可以是一个流程图，表示完成某项任务过程中各个步骤之间的次序关系，拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。排序依赖的原则就是各个步骤之间的优先关系。 拓扑排序得到的序列不一定是唯一的，因为某些步骤间没有规定优先关系（这就是偏序的特点），在拓扑排序的时候人为的加入一些规则，使得到的序列为满足偏序关系的一个全序。 拓扑排序的应用及其广泛。拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。21. 拓扑排序的定义拓扑排序：将有向图中的顶点排成一个拓扑有序序列。拓扑序列：有向图D的一个顶点序列称作一个拓扑序列。如果该序列中任两顶点v 、u ，若在D中v是u前趋，则在序列中v也是u前趋。 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 直观的看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。注意： 若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 若图中存在有向环，则不可能使顶点满足拓扑次序。 图 3 V5 V3 V2 V0 V1 V4 V6它的一个拓扑序列： V0, V1, V2, V4, V3, V6, V52.图的邻接表表示2.1邻接表的定义邻接表是图的一种链式存储结构。子啊邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于vi的边（对有向图是以顶点vi为尾的弧）。每个结点由三个域组成，其中邻接点域（adjvex）指示与顶点vi邻接的点在图中的位置，链域（nextarc）指示下一条边或弧的结点；数据域（info）存储和边或弧相关的信息，如权值等。每个链表上附设一个表头结点。在表头结点中，除了设有链域（firstarc）指向链表中的第一个结点之外，还设有存储顶点vi的名或其他有关信息的数据域（data）。如下图所示顶点数据指向第一个邻接顶点的指针datafirstarc4表头顶点的邻接顶点编号和边相关的信息指向下一个邻接顶点的指针 表结点结构adjvexweightnextarc 这些表头结点（可以链相接）通常以顺序结构的形式存储，以便随机访问任一顶点的链表。2.2邻接表的存储形式一个图的邻接表存储结构可形式地说明如下：#define MAX_VERTEX_NUM 20Typedef struct ArcNodeint adjvex; /该弧所指向的顶点位置struct ArcNode *nextarc; /指向下一条弧的指针InfoType *info; /该弧相关信息的指针ArcNode;typedef struct VNode VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM;Typedef struct AdjList vertices; int vexnum,arcnum; /图的当前顶点数和弧数 5int kind; /图的种类标志ALGraph;若无向图中有n个顶点、e条边，则它的邻接表需n个头结点和2e个表结点。显然，在稀疏的情况下，用邻接表表示图比邻接矩阵节省存储空间，当合边相关的信息较多时也是如此。2.3用邻接表构造有向图下标v02v1v2v345012334365v4v54565v66 图 由上图可以构造一个有向图。由上图可知，以顶点V0为尾的弧有,顶点V1为尾的弧有,两个，依次类推，可以根据弧来构造一个有向图。2.4有向图中顶点的入度由上图可知，在有向图中，第i个链表中的结点个数只是顶点vi6的出度，为求入度，必须遍历整个邻接表。在所有链表中其邻接点域的值为i的结点的个数是顶点vi的入度。以邻接表为存储结构，求有向图中顶点的入度的算法如下所示。int IndegreeG.vexnum=0; /临时存储各顶点的入度for(i=0; inextarc) Indegreep-adjvex+;3.拓扑排序3.1拓扑排序的方法在有向图中选一个没有前驱的顶点且输出之。从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点位置。后一种情况则说明有向图中存在环。3.2举例说明如图的有向图所示，图中，V0和V1没有前驱，则可任选一个。假设先输出V0，在删除V0及弧，之后，还有顶点V2和V1没有前驱，则任选一个，可先输出V1，在删除V1及弧,之后V2,V3,V4都没有前驱。依次类推，可从中任选一个继续进行。则最后得到该有向图的拓扑有序序列为：V0, V1, V2, V4, V3, V6, V5。74.在计算机中实现拓扑排序如何在计算机中实现？我们可采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree）。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点的入度减1来实现。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。拓扑排序的算法框架如下所示。1、扫描邻接表，计算各顶点的入度；2、将入度为0 的顶点入栈；3、while ( 栈非空 ) 将栈顶顶点v 弹出并输出之； 检查v的出边，将每条出边终点u的入度减1， 若u的入度变为0，则把u推入栈； 4、若输出的顶点数小于n，则输出“有回路”；否则拓扑排序正常结束。则拓扑排序的算法如下所示Status TopologicalSort(ALGraph G)/有向图G采用邻接表存储结构。8/若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返/回ERRORFindInDegree(G,indegree);/对各顶点求入度indegree0.vernum-1InitStack(S);for(i=0;inextarc) k=p-adivex; /对i号顶点的每个邻接点的入度减一 if(!(-indegreek) Push(S,k); /若入度为零，则入栈/for/whileif(countG.vexnum)9return ERROR; /该有向图有回路 else return OK;/TopologicalSort 分析上述算法，对有n个顶点和e条弧的有向图而言，建立求各顶点的入度的时间复杂度为O（e）；建零入度顶点栈的时间复杂度为O（n）；在拓扑排序过程中