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

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

2、列成一個(gè)線性序列的過(guò)程叫拓?fù)渑判?。拓?fù)渑判虻姆椒ǎ?在有向圖中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之。2從圖中刪除該頂點(diǎn)和所有以它為尾的弧。3重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(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、一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹?練習(xí)：拓?fù)渑判虻慕Y(jié)果不是唯一的，試寫(xiě)出下圖任意2個(gè)不同的拓?fù)湫蛄小?【解析】解題關(guān)鍵是弄清拓?fù)渑判虻牟襟E。（1）在AOV網(wǎng)中，選一個(gè)沒(méi)有前驅(qū)的結(jié)點(diǎn)且輸出；（2）刪除該頂點(diǎn)和以它為尾的??；（3）重復(fù)上述步驟直至全部頂點(diǎn)均輸出或不再有無(wú)前驅(qū)的頂點(diǎn)?！敬鸢浮?）0132465 2）0123465,關(guān)鍵路徑問(wèn)題提出：把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示

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

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

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

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