数据机构 课件第 7 章 图2

7.5 有向无环图及其应用一个无环的有向图称作有向无环图(DirectedAcyclineGraph)，简称DAG图以上三图都是有向图，其中左图为有向树，中图为DAG图((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)+cd*bb+a*d+ce*+d+ce**((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)b+a*d+c*e*+*设R为定义在集合X上的二元关系，如果对于每个x∈X，有xRx，那么称二元关系R是自反的在实数集合中，“≤〞是自反的，因为对于任意实数x≤x成立设R为定义在集合X上的二元关系，如果对于每个x，y∈X，每当xRy，就有yRx，那么称二元关系R是对称的平面上诸三角形集合中三角形的相似关系是对称的，因为假设三角形A相似三角形B，那么三角形B必然相似三角形A设R为定义在集合X上的二元关系，如果对于任意x，y，z∈X，每当xRy，yRz时，就有xRz，那么称二元关系R是传递的实数集合中，“≤〞、“＜〞、“＝〞都是传递的设R为定义在集合X上的二元关系，如果对于每个x，y∈X，每当xRy和yRx必有x=y，那么称二元关系R是反对称的实数集合中，“≤〞是反对称的，因为对于任意实数假设x≤y且y≤x必有x=y一.拓扑排序假设集合X上的关系R是自反的、反对称的和传递的，那么称R是集合X上的偏序关系设R是集合X上的偏序，如果对每个x，y∈X必有xRy或yRx，那么称R是集合X上的全序关系由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序(TopologicalSort)以下有向图中弧表示x≤yx，y〈〉V2V3V4V1偏序V2V1V3V4全序如此得到的全序称为拓扑有序一个表示偏序的有向图可用来表示一个流程图，图中每一条有向边表示两条子工程之间的次序关系(领先关系)C1C4C5C2C3C7C9C11C10C12C6C8用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(ActivityOnVertexNetwork)，简称AOV-网假设从顶点i到顶点j有一条有向路径，那么i是j的前驱，j是i的后继假设<i，j>是网中一条弧，那么i是j的直接前驱，j是i的直接后继C1C4C5C2C3C7C9C11C10C12C6C8(C1，C2，C3，C4，C5，C7，C9，C10，C11，C6，C12，C8)(C9，C10，C11，C6，C1，C12，C4，C2，C3，C5，C7，C8)V1V2V4V3V6V5V6V1V4V3V2V5V1V2V4V3V5V2V4V3V5V2V3V5ADBC输出A后DBCABCD0123ADCB∧32∧31∧∧adjvexnextarcinfodatafirstarc表结点头结点StatusTopologicalSort(ALGraphG){

FindInDegree(G，indegree)；

InitStack(S)； for(i=0；i<G.vexnum；++i) if(!indegree[i]) Push(S，i)； count=0；

… if(count<G.vexnum) returnERROR； else returnOK；}while(!StackEmpty(S)){

Pop(S，i)； printf(i，G.vertices[i].data)；//伪码 ++count； for(p=G.vertices[i].firstarc；p；p=p->nextarc) { k=p->adjvex； if(!(--indegree[k]))

Push(S，k)； }}V1V2V4V3V6V5V6V1V4V3V2V5V1V2V4V3V5V2V4V3V5V2V3V5StatusTopologicalSort(ALGraphG){

FindInDegree(G，indegree)；

InitStack(S)； for(i=0；i<G.vexnum；++i) if(!indegree[i]) Push(S，i)； count=0；

…… if(count<G.vexnum) returnERROR； else returnOK；}while(!StackEmpty(S)){

Pop(S，i)； printf(i，G.vertices[i].data)；//伪码 ++count； for(p=G.vertices[i].firstarc；p；p=p->nextarc) { k=p->adjvex； if(!(--indegree[k]))

Push(S，k)； }}拓扑排序算法时间复杂度O〔n+e〕二.关键路径AOE-网(ActivityOnEdge)即边表示活动的网AOE-网是一个带权的有向无环图，其中顶点表示事件(Event)弧表示活动权表示活动持续的时间V1V2V3V4V5V6V7a2=5a3=1a4=2a5=7a6=4a7=4a1=6由于在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度路径长度最长的路径叫做关键路径假设开始点是v1，从v1到vi的最长路径长度叫做事件vi的最早发生时间ve(i)V1V2V3V4V5V6V7a2=5a3=1a4=2a5=7a6=4a7=4a1=6ve(i)决定了所有以vi为尾的弧所表示的活动的最早开始时间用e(i)表示活动ai的最早开始时间用l(i)表示活动ai的最迟开始时间，l(i)是在不推迟整个工程完成的前提下，活动ai最迟必须开始进行的时间两者之差l(i)–e(i)意味着完成活动ai的时间余量，把l(i)=e(i)的活动叫做关键活动V1V2V3V4V5V6V7a2=5a3=1a4=2a5=7a6=4a7=4a1=6e(4)=5l(4)=8活动的最早开始时间e(i)活动的最迟开始时间l(i)事件的最早发生时间ve(i)事件的最迟发生时间vl(i)如果活动ai由弧表示，其持续时间记为dut()，则 e(i)=ve(j) l(i)=vl(k)–dut()j，k〈〉j，k〈〉j，k〈〉V1V2V3V4V5V6V7a2=5a3=1a4=2a5=7a6=4a7=4a1=6求事件的最早发生时间ve(i)从ve(0)=0开始向前递推ve(j)=Max{ve(i)+dut()}∈T，j=1，2，…，n–1其中，T是所有以第j个顶点为头的弧的集合i，j〈〉i，j〈〉iV1V2V3V4V5a2=5a3=8a4=4a5=4a1=6求事件的最迟发生时间vl(i)从vl(n–1)=ve(n–1)开始向后递推vl(i)=Min{vl(j)–dut()}∈S，j=1，2，…，n–1其中，S是所有以第i个顶点为尾的弧的集合i，j〈〉i，j〈〉jV2V3V4V5V1a3=2a4=9a5=3a1=4a2=6V2V5V4V6V1V3a4=3a7=2a8=1a3=2a1=3a2=2a5=4a6=30顶点vevlV1V2V3V4V5V632668042678010034342225666710110301活动ell–ea1a2a3a4a5a6a7a8√√√V4V6V1V3a7=2a2=2a5=4StatusToplogicalOrder(ALGraphG,stack&T){FindInDegree(G,indegree);InitStack(S);for(i=0；i<G.vexnum；++i)if(!indegree[i])

Push(S，i)；

InitStack(T);count=0;

ve[0..G.vexnum-1]=0;while(!StackEmpty(S)){……}if(count<G.vexnum)returnERROR;elsereturnOK;}while(!StackEmpty(S)){

Pop(S,j);

Push(T,j);

++count;for(p=G.vertices[j].firstarc;p;p=p->nextarc)

{

k=p>adjvex;if(--indegree[k]==0)

Push(S,k);if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);

}}statusCriticalPath(ALGraphG){if(!ToplogicalOrder(G,T))returnERROR;vl[0..G.vexnum-1]=ve[0..G.vexnum-1];while(!StackEmpty(T))//求各顶点vl值for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}……..//求ee，el和关键活动}//求ee，el和关键活动for(j=0;j<G.vexnum;++j)for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=*(p->info);

ee=ve[j];

el=vl[k]-dut;tag=(ee==el)?'*':'';printf(j,k,dut,ee,el,tag);}求关键路径的算法时间复杂度分析O〔n+e〕+O〔e〕＝O〔n+e〕

求关键路径的意义求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；假设一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。

Exercise 7对如下AOE网，试给出：⑴各活动的最早开始时间和最迟开始时间⑵该AOE网的关键路径v1v2v3v5v4v7v8v9v6v10a1=8a3=7a2=6a4=3a5=10a6=9a7=9a8=13a9=2a10=4a11=19a12=8a13=6a14=14a15=107.6 最短路径路径上的第一个顶点为源点(Source)，最后一个顶点为终点(Destination)一、从某个源点到其余各顶点的最短路径v5v0v4v1v3v21006030101055020迪杰斯特拉(Dijkstra)提出按路径长度递增的次序产生最短路径的算法引进一个辅助向量D，每个分量D[i]表示当前所找到的从始点v到每个终点vi的最短路径v=v0v5v0v4v1v3v2100603010105502012345D∞10∞30100长度为D[j]=Min{D[i]|vi∈V}的路径就是从v出发的长度最短的一条最短路径(v，vj)长度次短的路径的终点是vk，那么这条路径只能是以下二者之一：(v，vk)(v，vj，vk)假设S为已求得最短路径的终点的集合，那么可证明：下一条最短路径(设其终点为x)或者是弧(v，x)，或者是中间只经过S中的顶点而最后到达顶点x的路径假设S为已求得最短路径的终点的集合，那么可证明：下一条最短路径(设其终点为x)或者是弧(v，x)，或者是中间只经过S中的顶点而最后到达顶点x的路径证明：假设v到x的最短路径为(v，…，y，…，x)且此路径上有一个顶点y不在S中，那么说明存在一条终点不在S而长度比(v，…，y，…，x)更短的路径(v，…，y)但是，这是不可能的。即假设不成立下一条长度次短的最短路径的长度必是D[j]=Min{D[i]|vi∈V–S}其中，D[i]或者是弧(v，vi)上的权值，或者是D[k](vk∈S)和弧(vk，vi)上的权值之和设图以邻接矩阵arcs存储矩阵中各元素的值为各边的权值顶点间无边时其对应权值用无穷大表示。Dijkstra算法求最短路径的步骤〔1〕初始化：第一组〔集合s〕只含顶点v1,第二组〔集合t〕含有图中其余顶点。设一dist向量，其下标是各顶点，元素值是顶点v1到各顶点的边的权值。假设v1到某顶点无边，dist向量中的对应值为无穷大。〔2〕选dist中最小的权值，将其顶点〔j〕参加s集合。s=s∪{j}〔3〕修改从顶点v1到集合t(t=V-s)中各顶点的最短路径长度,如果dist[j]+arcs[j][k]<dist[k]那么修改dist[k]为dist[k]=dist[j]+arcs[j][k]〔4〕重复〔2〕、〔3〕n-1次。由此求得v1到图上其余各顶点得最短路径。

v5v0v4v1v3v21006030101055020v0v1v2v3v4v501234512345D∞10∞30100∞106030100∞10503090∞10503060∞10503060Dijkstra求最短路径的算法分析对于n个顶点的图，求一个顶点到其余顶点的最短路径，循环n-1次，加上修改最短路径的循环，是二层循环，故时间复杂度为O(n