算法拓扑排序学习教案

1、会计学1算法算法(sun f)拓扑排序拓扑排序第一页，共47页。第2页/共47页第二页，共47页。3 计划、施工过程、生产流程、程序流程等都是计划、施工过程、生产流程、程序流程等都是“工程工程”。除了很小的工程外，一般都把工程分为。除了很小的工程外，一般都把工程分为若干个叫做若干个叫做“活动活动”的子工程。完成了这些活动的子工程。完成了这些活动，这个工程就可以完成了。，这个工程就可以完成了。 例如，计算机专业学生的学习就是一个工程，每例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。

2、这样在有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先有的课程之间有领先(ln xin)关系，有的课程关系，有的课程可以并行地学习。可以并行地学习。第3页/共47页第三页，共47页。4例例课程代号课程代号 课程名称课程名称 先修棵先修棵C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,C4C11C3.C5C3,C6无无C9C9C1,C9,C10程序设计基础程序设计基础离散数学离散数学数据结构数据结构汇编语言汇编语言语言的设计和分析语言的设计和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学线性代数线性代数普通物理普通物理数值分

3、析数值分析C1C2C3C4C5C6C7C8C9C10C11C12第4页/共47页第四页，共47页。51 1、在、在AOVAOV中中拓扑有序序列：将各个顶点拓扑有序序列：将各个顶点 ( (代表各个活动代表各个活动) )排列成一个线性有排列成一个线性有序的序列，使得序的序列，使得AOVAOV网络中所有应存在的前驱和后继关系都能得网络中所有应存在的前驱和后继关系都能得到满足。到满足。拓扑排序拓扑排序(pi x)(pi x)把把AOVAOV网络中各顶点按照它们相互之间的网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。优先关系排列成一个线性序列的过程。检测检测AOVAOV网中是否存在环方

4、法：对有向图构造其顶点的拓扑有序网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该序列，若网中所有顶点都在它的拓扑有序序列中，则该AOVAOV网必网必定不存在环。定不存在环。二、拓扑二、拓扑(tu p)排序排序第5页/共47页第五页，共47页。6C1C2C3C4C5C6C7C8C9C10C11C12拓扑拓扑(tu p)序列：序列：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网的拓扑序列不是网的拓扑序列不是(b shi)唯

5、一的唯一的第6页/共47页第六页，共47页。7BDAC对于(duy)有向图不能求得它的拓扑(tu p)有序序列。因为图中存在一个(y )回路 B, C, D第7页/共47页第七页，共47页。8第8页/共47页第八页，共47页。abcghdfeabhcdgfe 没有前驱的顶点没有前驱的顶点(dngdin)删除顶点删除顶点(dngdin)及以它为及以它为尾的弧尾的弧 弧头顶弧头顶(tudng)点的入度减点的入度减1abcghdfe需要设一个数组indegreew，记录顶点(dngdin)的入度数 入度为零的顶点入度为零的顶点第9页/共47页第九页，共47页。10C0C1C2C3C4C5 C0 C1

6、 C2 C3 0 C4 C5 0012345ind data firstarc 130103 1adjvex next 3 0 5 1 5 0 0 1 5 0第10页/共47页第十页，共47页。11邻接邻接(ln ji)表结点：表结点：typedef struct node int adjvex; /顶点域顶点域 struct node *next; /链域链域JD;表头表头(bio tu)结点：结点：typedef struct tnode int ind; /入度域入度域 struct node *link; /链域链域TD;TD gM; 第11页/共47页第十一页，共47页。124 4、

7、拓扑排序算法、拓扑排序算法(sun f)(sun f)实现实现第12页/共47页第十二页，共47页。13例例1234560122inlink 5 5 4 3vex next3 2 5 2 4012345632104top16toptop第13页/共47页第十三页，共47页。140122inlink 5 5 4 3vex next3 2 5 2 40123456输出输出(shch)序列：序列：63210416toptop第14页/共47页第十四页，共47页。150122inlink 5 5 4 3vex next3 2 5 2 40123456输出序列：输出序列：6321041topp第15页/

8、共47页第十五页，共47页。160122inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6321041topp第16页/共47页第十六页，共47页。170122inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6321041topp第17页/共47页第十七页，共47页。180112inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6321041topp第18页/共47页第十八页，共47页。190112inlink 5 5

9、 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6321041topp=NULL第19页/共47页第十九页，共47页。200112inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 1321041toptop第20页/共47页第二十页，共47页。210112inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 132104topp第21页/共47页第二十一页，共47页。220102inlink 5 5 4 3vex next2 2 5 2

10、 40123456输出输出(shch)序列：序列：6 132104topp4第22页/共47页第二十二页，共47页。230102inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 132104p4top第23页/共47页第二十三页，共47页。240102inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 132104p4top第24页/共47页第二十四页，共47页。250002inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列

11、：序列：6 132104p4top3第25页/共47页第二十五页，共47页。260002inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 132104p4top3第26页/共47页第二十六页，共47页。270002inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 132104p4top3第27页/共47页第二十七页，共47页。280001inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 132104p4top3

12、第28页/共47页第二十八页，共47页。290001inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 132104p=NULL4top3第29页/共47页第二十九页，共47页。300001inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 1 3321044top3第30页/共47页第三十页，共47页。310001inlink 5 5 4 3vex next2 2 5 2 40123456输出输出(shch)序列：序列：6 1 3321044topp第31页/共47页第三十

13、一页，共47页。320001inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3321044topp第32页/共47页第三十二页，共47页。330001inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3321044topp第33页/共47页第三十三页，共47页。340000inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3321044topp2第34页/共47页第三十四页，共47页。350000

14、inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3321044topp2第35页/共47页第三十五页，共47页。360000inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3321044top2p=NULL第36页/共47页第三十六页，共47页。370000inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3 2321044top2p=NULL第37页/共47页第三十七页，共47页。380000

15、inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3 2321044topp=NULL第38页/共47页第三十八页，共47页。390000inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3 2 4321044top第39页/共47页第三十九页，共47页。400000inlink 5 5 4 3vex next1 2 5 2 40123456输出输出(shch)序列：序列：6 1 3 2 432104topp第40页/共47页第四十页，共47页。410000inl

16、ink 5 5 4 3vex next0 2 5 2 40123456输出输出(shch)序列：序列：6 1 3 2 432104topp5第41页/共47页第四十一页，共47页。420000inlink 5 5 4 3vex next0 2 5 2 40123456输出输出(shch)序列：序列：6 1 3 2 4 532104topp=NULL第42页/共47页第四十二页，共47页。430000inlink 5 5 4 3vex next0 2 5 2 40123456输出输出(shch)序列：序列：6 1 3 2 432104topp=NULL5第43页/共47页第四十三页，共47页。440000inlink 5 5 4 3vex next0 2 5 2 40