算法9拓扑排序课件

1拓扑排序

一、概念1、有向无环图DAG(DirectedAcyclicGraph)

无环的有向图2、AOV(ActivityOnVertices)网络：用顶点表示活动，用有向弧<Vi,Vj>表示活动间的优先关系。Vi必须先于活动Vj进行。这种有向图称为用顶点表示活动的网络。若<vi,vj>是图中有向边，则vi是vj的直接前驱；vj是vi的直接后继AOV网中不允许有回路，这意味着某项活动不能以自己为先决条件4计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动，这个工程就可以完成了。例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。5例课程代号课程名称先修棵C1C2C3C4C5C6C7C8C9C10C11C12无C1C1,C2C1C3,C4C11C3.C5C3,C6无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C1261、在AOV中拓扑有序序列：将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。检测AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。二、拓扑排序7C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一个AOV网的拓扑序列不是唯一的8BDAC对于有向图不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}9

输入AOV网络。有n个顶点。

1在AOV网络中选一个没有直接前驱的顶点，并输出之。2从图中删去该顶点,同时删去所有它发出的有向边。3重复以上1、2

步,直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。abcghdfeabhcdgfe

没有前驱的顶点删除顶点及以它为尾的弧

弧头顶点的入度减1abcghdfe需要设一个数组indegree[w]，记录顶点的入度数

入度为零的顶点113、AOV网络的存储方式--邻接表表示C0C1C2C3C4C5

C0C1C2C30C4C50012345ind

datafirstarc

1301031adjvexnext305150015012邻接表结点：typedefstructnode{intadjvex;//顶点域

structnode*next;//链域}JD;表头结点：typedefstructtnode{intind;//入度域

structnode*link;//链域}TD;TDg[M];

AOV网络的存储方式--邻接表表示131把邻接表中所有入度为0的顶点进栈2栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈3重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。4、拓扑排序算法实现14例1234560122inlink5543^^^vexnext3^25^240123456^32104top16toptop150122inlink5543^^^vexnext3^25^240123456^输出序列：63210416toptop160122inlink5543^^^vexnext3^25^240123456^输出序列：6321041topp170122inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp180122inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp190112inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp200112inlink5543^^^vexnext2^25^240123456^输出序列：6321041topp=NULL210112inlink5543^^^vexnext2^25^240123456^输出序列：61321041toptop220112inlink5543^^^vexnext2^25^240123456^输出序列：6132104topp230102inlink5543^^^vexnext2^25^240123456^输出序列：6132104topp4240102inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top250102inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top260002inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top3270002inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top3280002inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top3290001inlink5543^^^vexnext2^25^240123456^输出序列：6132104p4top3300001inlink5543^^^vexnext2^25^240123456^输出序列：6132104p=NULL4top3310001inlink5543^^^vexnext2^25^240123456^输出序列：613321044top3320001inlink5543^^^vexnext2^25^240123456^输出序列：613321044topp330001inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp340001inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp350000inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp2360000inlink5543^^^vexnext1^25^240123456^输出序列：613321044topp2370000inlink5543^^^vexnext1^25^240123456^输出序列：613321044top2p=NULL380000inlink5543^^^vexnext1^25^240123456^输出序列：6132321044top2p=NULL390000inlink5543^^^vexnext1^25^240123456^输出序列：6132321044topp=NULL400000inlink5543^^^vexnext1^25^240123456^输出序列：61324321044top410000inlink5543^^^vexnext1^25^240123456^输出序列：6132432104topp420000inlink5543^^^vexnext0^25^240123456^输出序列：6132432104topp5430000inlink5543^^^vexnext0^25^240123456^输出序列：61324532104topp=NULL440000inlink5543^^^vexnext0^25^240123456^输出序列：6132432104topp=NULL5450000inlink5543^^^vexnext0^25^240123456^输出序列：61324532104top5