数据结构第七章第五节

数据结构第七章第五节第1页，课件共55页，创作于2023年2月应用一:描述含有公共子式的表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)第2页，课件共55页，创作于2023年2月应用二:描述工程或系统的进行过程工程(Project)活动

(Activity)两个问题:

工程是否能顺利完成?

工程完成所必需的最短时间?第3页，课件共55页，创作于2023年2月7.5.1拓扑排序TopologicalSort?偏序全序全序偏序第4页，课件共55页，创作于2023年2月课程编号课程名称C1程序设计基础C2离散数学C3数据结构C4汇编语言C1C5语言的设计和分析C3,C4C6计算机原理C11C7编译原理C5,C3C8操作系统C3,C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9,C10,C1

AOV网

---ActivityonVertexNetwork

顶点----活动弧----优先关系先决条件无C1,C2C1C12C11C10C1C4C2C3C9C5C7C8C6第5页，课件共55页，创作于2023年2月拓扑排序的方法（1）在有向图中选一个没有前驱的顶点且输出之（2）从图中删除该顶点且以它为尾的弧V1V2V4V3V6V5第6页，课件共55页，创作于2023年2月拓扑排序的方法（1）在有向图中选一个没有前驱的顶点且输出之（2）从图中删除该顶点且以它为尾的弧V6V1V2V4V3V6V5V6第7页，课件共55页，创作于2023年2月V1拓扑排序的方法（1）在有向图中选一个没有前驱的顶点且输出之（2）从图中删除该顶点且以它为尾的弧V6V2V4V3V5V1V1V1第8页，课件共55页，创作于2023年2月拓扑排序的方法（1）在有向图中选一个没有前驱的顶点且输出之（2）从图中删除该顶点且以它为尾的弧V6V2V4V3V5V1V4V4第9页，课件共55页，创作于2023年2月拓扑排序的方法（1）在有向图中选一个没有前驱的顶点且输出之（2）从图中删除该顶点且以它为尾的弧V6V2V3V5V1V4V3V3V2V5第10页，课件共55页，创作于2023年2月V1V2V4V3V6V5V1V2V4V3V6V5V1V2V4V3V5V2V4V3V5回路!!!第11页，课件共55页，创作于2023年2月StatusTopologicalSort(ALGraphG){//有向图采用邻接表存储结构

FindInDegree(G,indegree);

//对各顶点求入度indegree[0..vernum-1]InitStack(S);for(i=0;i<G.vexnum;++i)//建零入度顶点栈

if(!Indegree[i])Push(S,i);//入度为0者进栈

count=0;//对输出顶点记数

while(!StackEmpty(S)){Pop(S,i);printf(i,G.vertices[i].data);++count;//输出i号顶点并计数

for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;//对i号顶点的每个邻接点的入度减1if(!(--indegree[k])Push(S,k);//若入度减为零,则入栈

}//for}//while

if(count<G.vexnum)returnERROR;

//该有向图有回路

elsereturnOK;}//TopologicalSort

第12页，课件共55页，创作于2023年2月

3114V1

V2V3

V4

0123V5

4V6

52434FingIndegree(ALGraphG,intindegree[])思考：如何实现？第13页，课件共55页，创作于2023年2月

3114V1

V2V3

V4

0123V5

4V6

52434FingIndegree(ALGraphG,intindegree[])021230第14页，课件共55页，创作于2023年2月e(i):活动ai的最早开始时间l(i):活动ai的最迟开始时间7.5.2关键路径顶点:

事件弧:

活动权:

持续时间ActivityOnEdgeAOE网源点汇点关键活动：e(i)=l(i)V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第15页，课件共55页，创作于2023年2月7.5.2关键路径源点汇点V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4顶点:

事件弧:

活动权:

持续时间ActivityOnEdgeAOE网e(i):活动ai的最早开始时间l(i):活动ai的最迟开始时间关键活动：e(i)=l(i)第16页，课件共55页，创作于2023年2月V0V1V2a1=15烧开水找茶叶洗杯子泡茶a2=3a3=5a4=5开始准备开始泡茶喝上茶水“喝茶水”第17页，课件共55页，创作于2023年2月活动ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9顶点vevl求关键路径的过程第18页，课件共55页，创作于2023年2月活动ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660000203664658777771016161414a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9顶点vevl求关键路径的过程第19页，课件共55页，创作于2023年2月顶点vevl活动ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660000203664658777771016161414000000a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9求关键路径的过程第20页，课件共55页，创作于2023年2月顶点vevl活动ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660000203664658777771016161414000000a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9求关键路径的过程第21页，课件共55页，创作于2023年2月(1)从ve(0)=0开始向前递推ve(j)ve(1)ve(2)…ve(i)求关键路径的步骤拓扑排序a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9第22页，课件共55页，创作于2023年2月求关键路径的步骤(2)从vl(n-1)=ve(n-1)开始向后递推vl(i)vl(1)vl(2)…vl(j)逆拓扑排序a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9第23页，课件共55页，创作于2023年2月求关键路径的步骤(3)求关键路径a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9第24页，课件共55页，创作于2023年2月StatusTopologicalSort(ALGraphG){

//有向网采用邻接矩阵结构,求各顶点事件的最早发生时间veFindInDegree(G,indegree);InitStack(S);//S为零入度顶点栈

建零入度顶点栈;InitStack(T);//T为拓扑序列顶点栈

count=0;ve[0..G.vexnum-1]=0;//初始化

while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;//j号顶点入T栈并计数

for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;//对i号顶点的每个邻接点的入度减1if(!(--indegree[k])Push(S,k);//若入度减为零,则入栈

if(ve[j]+*(p->info)>ve[k])ve[k]=ve[j]+*(p->info);}//for*(p->info)=dut<j,k>}//whileif(count<G.vexnum)returnERROR;elsereturnOK;}//TopologicalOrder第25页，课件共55页，创作于2023年2月StatusCriticalPath(ALGraphG){

//G为有向网,输出G的各项关键活动

if(!TopologicalOrder(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);//dut<j,k>

if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}//forfor(j=0;j<G.vexnum;++j)//求ee,el和关键活动

for(p=G.vertices[j];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);//输出关键活动

}}//CriticalPath

第26页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110STv100000000第27页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110STv100000000第28页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110STv1v2000000006第29页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v300000004第30页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v3v400000405第31页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v45000007第32页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v45v6000007第33页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6000011第34页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6500011第35页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v600v51157第36页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v600v5711第37页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v600v5711v716第38页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v60v57v7v8161114第39页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v7v81601814第40页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v618v57v7v8v9161814第41页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v618v57v7v8v9161814第42页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v7v8161814181818181818181818v9第43页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v7v8161814181818181818181818第44页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v816181418181818181818181816第45页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v571618141818181818181818181614第46页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6716181418181818181818181816147第47页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v67161814181818181818181818161477第48页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v34v457v671618141818181818181818181614776第49页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv14v457v6716181418181818181818181816147766第50页，课件共55页，创作于2023年2月V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)顶点活动v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106