《数据结构》课件第六章.ppt

*源点和汇点的概念画图说明各个定义*最迟发生时间——保证整个工程的前提下，活动不能最迟开始的时间*最迟发生时间——保证整个工程的前提下，活动不能最迟开始的时间*Ve是事件的最早发生时间，vl是事件的最晚发生时间拓扑排序拓扑排序：由某个集合上的一个偏序得到该集合上的一个全序的过程。偏序：若集合X上的关系R是自反的、反对称的、传递的，则称R是集合X上的偏序关系。全序：设R是集合X上的偏序，如果对每个x,y∈X，必有xRy或yRx，则称R是集合X上的全序关系。性质比较：偏序中仅有部分成员之间可以比较全序中所有成员之间都可以比较AOV-网AOV-网——用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(ActivityOnVertexNet-work),简称AOV-网。AOV-网中不能存在环，因此应首先判断AOV-网中是否存在环。拓扑排序的步骤1.在有向图中选一个没有前驱的顶点且输出之。2.从图中删除该点和所有以它为尾的弧。3.重复上述两步，直至所有顶点均已输出，或当前图中不存在无前驱的顶点为止；若不存在没有前驱的顶点则该有向图中存在环。若输出的结点个数小于有向图中的结点个数，则该有向图有回路关键路径★AOE-网：与AOV-网对应，即边表示活动的网。AOE-网是一个带权的有向无环图在AOE-网中，顶点表示事件，弧表示活动，权表示活动持续的时间，AOE-网通常用来估算工程完成的时间在AOE-网中，只有一个入度为零的点（称为源点），有一个出度为零的点（汇点）。在AOE-网中要解决两个问题：完成整项工程需要的时间哪些活动是影响工程进度的关键关键路径：从源点到汇点的路径长度最长的路径。关键路径上的所有活动都是关键活动。结点的最早发生时间Ve(1)=0Ve(i)=Max{Ve(k)+Wki}(Vk,Vi)∈ET(总周期)=Ve(n)v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=2Ve(5)=max{6+1,4+1}=7Ve(8)=max{7+7,7+4}=14结点的最迟发生时间Vl(i)=Min{Vl(j)-Wij}(Vi,Vj)∈EVl(n)=Ve(n)=T(总周期)★若Vl(m)=Ve(m)，则点m是关键点。v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=2边的最早开工时间Ee(ij)=Ve(i)边的最迟开工时间El(ij)=Vl(j)–Wij★关键活动即满足El(ij)=Ee(ij)的边1814161078660Vl181416775460Ve987654321Ve是某个事件的最早发生时间，从第一个时间开始推Vl是某个事件最晚发生时间，从最后一个事件逆推v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=2a1a2a3a4a5a6a7a8a9a10a11Ee0006457771614El02366877101614v1v2v3v5v7v8v9v4v6a6=2a2=4a3=5a4=1a1=6a5=1a7=9a8=7a9=4a11=4a10=21814161078660Vl181416775460Ve987654321Ee(ij)=Ve(i)El(ij)=Vl(j)–Wij图的应用三——最短路径实际应用——交通网，中转次数最少的路线模型抽象：采用带权有向图源点：路径上的第一个结点。终点：路径上的最后一个结点。从某个源点到其余各顶点的最短路径——迪杰斯特拉算法迪杰斯特拉算法算法步骤：1.假设S为最短路径以确定的顶点集，V-S是最短路径尚未确定的顶点集。D[v]为u到v的最短路径长度，初始时，将源点u放入S中2.D[v]=w(u,v)(v∈V-S)3.选取点k∈V-S，使得D[k]=min{D[t]:t∈V-S}4.将k添入S5.重新计算D[v]值，其中v∈V-S，t∈S：如果D[