數(shù)據(jù)結(jié)構(gòu)第七章第五節(jié)

數(shù)據(jù)結(jié)構(gòu)第七章第五節(jié)第一頁，共五十五頁，2022年，8月28日應(yīng)用一:描述含有公共子式的表達(dá)式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)第二頁，共五十五頁，2022年，8月28日應(yīng)用二:描述工程或系統(tǒng)的進(jìn)行過程工程(Project)活動(dòng)

(Activity)兩個(gè)問題:

工程是否能順利完成?

工程完成所必需的最短時(shí)間?第三頁，共五十五頁，2022年，8月28日7.5.1拓?fù)渑判騎opologicalSort?偏序全序全序偏序第四頁，共五十五頁，2022年，8月28日課程編號(hào)課程名稱C1程序設(shè)計(jì)基礎(chǔ)C2離散數(shù)學(xué)C3數(shù)據(jù)結(jié)構(gòu)C4匯編語言C1C5語言的設(shè)計(jì)和分析C3,C4C6計(jì)算機(jī)原理C11C7編譯原理C5,C3C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9,C10,C1

AOV網(wǎng)

---ActivityonVertexNetwork

頂點(diǎn)----活動(dòng)弧----優(yōu)先關(guān)系先決條件無C1,C2C1C12C11C10C1C4C2C3C9C5C7C8C6第五頁，共五十五頁，2022年，8月28日拓?fù)渑判虻姆椒ǎ?）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之（2）從圖中刪除該頂點(diǎn)且以它為尾的弧V1V2V4V3V6V5第六頁，共五十五頁，2022年，8月28日拓?fù)渑判虻姆椒ǎ?）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之（2）從圖中刪除該頂點(diǎn)且以它為尾的弧V6V1V2V4V3V6V5V6第七頁，共五十五頁，2022年，8月28日V1拓?fù)渑判虻姆椒ǎ?）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之（2）從圖中刪除該頂點(diǎn)且以它為尾的弧V6V2V4V3V5V1V1V1第八頁，共五十五頁，2022年，8月28日拓?fù)渑判虻姆椒ǎ?）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之（2）從圖中刪除該頂點(diǎn)且以它為尾的弧V6V2V4V3V5V1V4V4第九頁，共五十五頁，2022年，8月28日拓?fù)渑判虻姆椒ǎ?）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之（2）從圖中刪除該頂點(diǎn)且以它為尾的弧V6V2V3V5V1V4V3V3V2V5第十頁，共五十五頁，2022年，8月28日V1V2V4V3V6V5V1V2V4V3V6V5V1V2V4V3V5V2V4V3V5回路!!!第十一頁，共五十五頁，2022年，8月28日StatusTopologicalSort(ALGraphG){//有向圖采用鄰接表存儲(chǔ)結(jié)構(gòu)

FindInDegree(G,indegree);

//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]InitStack(S);for(i=0;i<G.vexnum;++i)//建零入度頂點(diǎn)棧

if(!Indegree[i])Push(S,i);//入度為0者進(jìn)棧

count=0;//對(duì)輸出頂點(diǎn)記數(shù)

while(!StackEmpty(S)){Pop(S,i);printf(i,G.vertices[i].data);++count;//輸出i號(hào)頂點(diǎn)并計(jì)數(shù)

for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1if(!(--indegree[k])Push(S,k);//若入度減為零,則入棧

}//for}//while

if(count<G.vexnum)returnERROR;

//該有向圖有回路

elsereturnOK;}//TopologicalSort

第十二頁，共五十五頁，2022年，8月28日

3114V1

V2V3

V4

0123V5

4V6

52434FingIndegree(ALGraphG,intindegree[])思考：如何實(shí)現(xiàn)？第十三頁，共五十五頁，2022年，8月28日

3114V1

V2V3

V4

0123V5

4V6

52434FingIndegree(ALGraphG,intindegree[])021230第十四頁，共五十五頁，2022年，8月28日e(i):活動(dòng)ai的最早開始時(shí)間l(i):活動(dòng)ai的最遲開始時(shí)間7.5.2關(guān)鍵路徑頂點(diǎn):

事件弧:

活動(dòng)權(quán):

持續(xù)時(shí)間ActivityOnEdgeAOE網(wǎng)源點(diǎn)匯點(diǎn)關(guān)鍵活動(dòng)：e(i)=l(i)V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第十五頁，共五十五頁，2022年，8月28日7.5.2關(guān)鍵路徑源點(diǎn)匯點(diǎn)V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4頂點(diǎn):

事件弧:

活動(dòng)權(quán):

持續(xù)時(shí)間ActivityOnEdgeAOE網(wǎng)e(i):活動(dòng)ai的最早開始時(shí)間l(i):活動(dòng)ai的最遲開始時(shí)間關(guān)鍵活動(dòng)：e(i)=l(i)第十六頁，共五十五頁，2022年，8月28日V0V1V2a1=15燒開水找茶葉洗杯子泡茶a2=3a3=5a4=5開始準(zhǔn)備開始泡茶喝上茶水“喝茶水”第十七頁，共五十五頁，2022年，8月28日活動(dòng)ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9頂點(diǎn)vevl求關(guān)鍵路徑的過程第十八頁，共五十五頁，2022年，8月28日活動(dòng)ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660000203664658777771016161414a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9頂點(diǎn)vevl求關(guān)鍵路徑的過程第十九頁，共五十五頁，2022年，8月28日頂點(diǎn)vevl活動(dòng)ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660000203664658777771016161414000000a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9求關(guān)鍵路徑的過程第二十頁，共五十五頁，2022年，8月28日頂點(diǎn)vevl活動(dòng)ell-ev1v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110645771614181814161078660000203664658777771016161414000000a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9求關(guān)鍵路徑的過程第二十一頁，共五十五頁，2022年，8月28日(1)從ve(0)=0開始向前遞推ve(j)ve(1)ve(2)…ve(i)求關(guān)鍵路徑的步驟拓?fù)渑判騛1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9第二十二頁，共五十五頁，2022年，8月28日求關(guān)鍵路徑的步驟(2)從vl(n-1)=ve(n-1)開始向后遞推vl(i)vl(1)vl(2)…vl(j)逆拓?fù)渑判騛1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9第二十三頁，共五十五頁，2022年，8月28日求關(guān)鍵路徑的步驟(3)求關(guān)鍵路徑a1=6a2=4a3=5a6=2a9=4a8=7a7=9a4=1a5=1a10=2a11=4V1V8V4V6V3V2V5V7V9第二十四頁，共五十五頁，2022年，8月28日StatusTopologicalSort(ALGraphG){

//有向網(wǎng)采用鄰接矩陣結(jié)構(gòu),求各頂點(diǎn)事件的最早發(fā)生時(shí)間veFindInDegree(G,indegree);InitStack(S);//S為零入度頂點(diǎn)棧

建零入度頂點(diǎn)棧;InitStack(T);//T為拓?fù)湫蛄许旤c(diǎn)棧

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

while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;//j號(hào)頂點(diǎn)入T棧并計(jì)數(shù)

for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減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第二十五頁，共五十五頁，2022年，8月28日StatusCriticalPath(ALGraphG){

//G為有向網(wǎng),輸出G的各項(xiàng)關(guān)鍵活動(dòng)

if(!TopologicalOrder(G,T))returnERROR;vl[0..G.vexnum-1]=ve[0..G.vexnum-1];//初始化各頂點(diǎn)的最遲發(fā)生時(shí)間

while(!StackEmpty(T))//按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的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和關(guān)鍵活動(dòng)

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);//輸出關(guān)鍵活動(dòng)

}}//CriticalPath

第二十六頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110STv100000000第二十七頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110STv100000000第二十八頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a110STv1v2000000006第二十九頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v300000004第三十頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v3v400000405第三十一頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v45000007第三十二頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v45v6000007第三十三頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6000011第三十四頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6500011第三十五頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v600v51157第三十六頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v600v5711第三十七頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v600v5711v716第三十八頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v60v57v7v8161114第三十九頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v7v81601814第四十頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v618v57v7v8v9161814第四十一頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v618v57v7v8v9161814第四十二頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v7v8161814181818181818181818v9第四十三頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v7v8161814181818181818181818第四十四頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v57v816181418181818181818181816第四十五頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6v571618141818181818181818181614第四十六頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v6716181418181818181818181816147第四十七頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v2v34v457v67161814181818181818181818161477第四十八頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv1v34v457v671618141818181818181818181614776第四十九頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106STv14v457v6716181418181818181818181816147766第五十頁，共五十五頁，2022年，8月28日V1V2V4V3V5V6V8V9V7a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4v1ve(i)vl(i)e(i)l(i)頂點(diǎn)活動(dòng)v2v3v4v5v6v7v8v9a1a2a3a4a5a6a7a8a9a10a1106S