资源描述:
《dag图和关键路径》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、普里姆(Prim)算法4316504535562217431650453556221702143165045355622170214021543165045355622170214021540532210214021543165045355622174053221410535221431045352214316504535562217021402154053221410535221设N=(V,E,C)为连通网,TE是N的最小支撑树的边的集合。①算法开始时,U={uo}(uo∈V),TE=○;②找到满足weight(u,v)=mi
2、n{weight(u1,v1)
3、u1∈U,v1∈V-U},的边,把它并入集合TE中,v同时并入U。③反复执行②,直至V=U时终止算法。[例]1104532104532123104532210431453221431045352214316504535562217克鲁斯卡尔(Kruskar)算法设连通网N=(V,E,C),T为N的最小支撑树。初始时T={V,{○}},即T中没有边,只有n个顶点就是n个连通分量。①在E中选择权值最小的边,将此边从E中删除。②如果此边的两个顶点在T的不同的连通分量中,则将此边加入到T中,从而导致T中减
4、少一个连通分量;如果此边的两个顶点在同一个连通分量中,则重复执行①②,直至T中仅剩一个连通分量时,终止操作。7.5拓扑排序7.5.1基本概念AOV网:在有向图中,用顶点表示活动,用有向边表示活动之间的先后关系,称这样的有向图为AOV网(ActivityOnVertexNetwork)。例如,计算机专业学生的学习就是一个工程,每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程,有些则不要求。这样在有的课程之间有领先关系,有的课程可以并行地学习。[例]计算机专业必修课程安排计算机专业必修课程课程代号课程名称先修课程C0
5、高等数学无C1程序设计基础无C2离散数学C0,C1C3数据结构C2,C4C4程序设计语言C1C5编译技术C3,C4C6操作系统C3,C8C7普通物理C0C8计算机原理C7C0C2C3C5C4C1C7C6C87.5拓扑排序7.5.1基本概念AOV网:在有向图中,用顶点表示活动,用有向边表示活动之间的先后关系,称这样的有向图为AOV网(ActivityOnVertexNetwork)。计划、施工过程、生产流程、程序流程等都是“工程”。除了很小的工程外,一般都把工程分为若干个叫做“活动”的子工程。完成了这些活动,这个工程就可以完成了。
6、在AOV网络中,如果活动ai必须在活动aj之前进行,则存在有向边,AOV网络中不能出现有向回路,即有向环。在AOV网络中如果出现了有向环,则意味着某项活动应以自己作为先决条件。因此,对给定的AOV网络,必须先判断它是否存在有向环。拓扑序列:就是把AOV网中的所有顶点排成一个线性序列,使每个活动的所有前驱活动都排在该活动的前边。拓扑排序:构造AOV网的拓扑序列的过程被称为拓扑排序。拓扑排序算法基本步骤①从网中选择一个入度为0的顶点且输出之。②从网中删除该顶点及其所有出边。③执行①②,直至所有顶点已输出,或网中剩余顶点
7、入度均不为0为止。例如,对学生选课工程图进行拓扑排序:C6C0C2C3C5C4C1C7C8得到的某拓扑有序序列为C0,C1,C2,C4,C3,C5,C7,C8,C6或C0,C7,C8,C1,C4,C2,C3,C6,C5结果:对于任何无回路的AOV网,其所有顶点均可排成拓扑序列,并且其拓扑序列未必唯一。思考:利用拓扑排序可以检查AOV网是否存在环路,到底是通过什么方式检查的呢?再例如,对学生选课工程图进行拓扑排序:C6C0C2C3C5C4C1C7C8得到的拓扑有序序列为C0,C1,C2,C7,C8结果:对于任何无回路的AOV网,其
8、所有顶点均可排成拓扑序列,并且其拓扑序列未必唯一。结论:如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中,则该AOV网络中必定不会出现有向环;相反,如果得不到满足要求的拓扑有序序列,则说明AOV网络中存在有向环,此AOV网络所代表的工程是不可行的。7.5.2剖析拓扑排序算法[例]325140002123013425indegree0243152∧42∧3∧53∧5∧5∧拓扑排序算法描述:325140InitStack(S);for(i=0;i9、e[i])Push(S,i);//入度为0者进栈count=0;//对输出顶点计数002123013425top00stack初始top=-1indegree拓扑排序算法描述:325140InitStack(S);for(i=0;i