數(shù)據(jù)結(jié)構(gòu)第13周

1、拓?fù)渑判騿栴}提出：學(xué)生選修課程問題，學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)。,拓?fù)渑判?解決方案：定義一個AOV網(wǎng)，用頂點(diǎn)表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動的網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng)。,例如：用頂點(diǎn)表示上一張課程表的課程，用有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧,拓?fù)渑判颍喊袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排

2、列成一個線性序列的過程叫拓?fù)渑判?。拓?fù)渑判虻姆椒ǎ?在有向圖中選一個沒有前驅(qū)的頂點(diǎn)且輸出之。2從圖中刪除該頂點(diǎn)和所有以它為尾的弧。3重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。,拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或 ：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8,注意：

3、一個AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹?練習(xí)：拓?fù)渑判虻慕Y(jié)果不是唯一的，試寫出下圖任意2個不同的拓?fù)湫蛄小?【解析】解題關(guān)鍵是弄清拓?fù)渑判虻牟襟E。（1）在AOV網(wǎng)中，選一個沒有前驅(qū)的結(jié)點(diǎn)且輸出；（2）刪除該頂點(diǎn)和以它為尾的??；（3）重復(fù)上述步驟直至全部頂點(diǎn)均輸出或不再有無前驅(qū)的頂點(diǎn)?！敬鸢浮?）0132465 2）0123465,關(guān)鍵路徑問題提出：把工程計劃表示為有向圖，用頂點(diǎn)表示事件，弧表示

4、活動；每個事件表示在它之前的活動已完成，在它之后的活動可以開始。,例 設(shè)一個工程有11項(xiàng)活動，9個事件事件V1——表示整個工程開始事件V9——表示整個工程結(jié)束問題：（1）完成整項(xiàng)工程至少需要多少時間？ （2）哪些活動是影響工程進(jìn)度的關(guān)鍵？,解決方案：AOE網(wǎng)(Activity On Edge)，也叫邊表示活動的網(wǎng)。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動，權(quán)表示活動持續(xù)時間。路徑長度——路徑上各活

5、動持續(xù)時間之和關(guān)鍵路徑——路徑長度最長的路徑Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間e(i)——表示活動ai的最早開始時間l(i)——表示活動ai的最遲開始時間l(i)-e(i)——表示完成活動ai的時間余量關(guān)鍵活動即為關(guān)鍵路徑上的活動，也就是l(i)=e(i)的活動,求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計算l(i)-e(i),V1V2V3V4

6、V5V6V7V8V9,064577161418,0668710161418,,,a1a2a3a4a5a6a7a8a9a10a11,??????,選擇題,關(guān)鍵路徑是（　?。〢） AOE網(wǎng)中從源點(diǎn)到匯點(diǎn)的最長路徑B） AOE網(wǎng)中從源點(diǎn)到匯點(diǎn)的最短路徑C） AOV網(wǎng)中從源點(diǎn)到匯點(diǎn)的最長路徑D） AOV網(wǎng)中從源點(diǎn)到匯點(diǎn)的最短路徑,A,練習(xí)：寫出求以下AOE

7、網(wǎng)的關(guān)鍵路徑的過程。要求：給出每一個事件和每一個活動的最早開始時間和最晚開始時間。,,解析：,1）求事件的最早發(fā)生時間ve(j), 最晚發(fā)生時間vl(j);2）最早發(fā)生時間從ve(0)開始按拓?fù)渑判蛳蚯斑f推到ve(6), 最晚發(fā)生時間從vl(6)按逆拓?fù)渑判蛳蚝筮f推到vl(0);3）計算e(i),l(i)：設(shè)ai由弧表示，持續(xù)時間記為dut，則有下式成立 e(i)=ve(j)