數據結構第七章第五節第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