數(shù)據(jù)結(jié)構(gòu)-第七章-圖7.2

7.5

有向無環(huán)圖及其應(yīng)用一、有向無環(huán)圖二、拓?fù)渑判蛉?、關(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第1頁。數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第3頁。AOV網(wǎng)(ActivityOnVertexNetwork)

用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱AOV網(wǎng)。7.5

有向無環(huán)圖及其應(yīng)用二、拓?fù)渑判騿栴}提出：學(xué)生選修課程問題頂點(diǎn)——表示課程有向弧——表示先決條件，若課程i是j的先決條件，則圖中有弧<i,j>學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第4頁。拓?fù)渑判虻亩x

所謂拓?fù)湫蛄?，就是把AOV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，該序列滿足如下條件：若AOV網(wǎng)中存在弧<vi,vj>，則在該序列中，vi必位于vj之前。構(gòu)造AOV網(wǎng)的拓?fù)湫蛄械牟僮鞅环Q為拓?fù)渑判颉?/p>

7.5

有向無環(huán)圖及其應(yīng)用二、拓?fù)渑判驍?shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第5頁。a.在有向圖中選一個(gè)沒有前驅(qū)(入度為0)的頂點(diǎn)且輸出之。b.從圖中刪除該頂點(diǎn)及所有以它為尾的弧。c.重復(fù)執(zhí)行a和b，直到全部頂點(diǎn)均已輸出，或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止。7.5

有向無環(huán)圖及其應(yīng)用二、拓?fù)渑判?.如何進(jìn)行拓?fù)渑判颍繑?shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第6頁。示例拓?fù)湫蛄校簐0-v3-v2-v4-v17.5

有向無環(huán)圖及其應(yīng)用二、拓?fù)渑判?/p>

v0-v2-v3-v4-v1v0-v2-v3-v1-v4

v0-v2-v1-v3-v4v0-v3-v2-v1-v4結(jié)論：一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏臄?shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第7頁。a.采用鄰接表作有向圖的存儲(chǔ)結(jié)構(gòu)，且在頭結(jié)點(diǎn)增加一個(gè)存放頂點(diǎn)入度的分量(indegree)。7.5

有向無環(huán)圖及其應(yīng)用二、拓?fù)渑判?.拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)b.把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧c.棧非空時(shí)，輸出棧頂元素Vj并出棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1，即indegree[k]-1；若Vk的入度為0則進(jìn)棧。重復(fù)c操作直至?？諡橹?。若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叀?shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第8頁。7.5

有向無環(huán)圖及其應(yīng)用二、拓?fù)渑判?/p>

算法描述例123456輸出序列：6132450122indegreefirst4432^^^adjvexnext3^14^130123456^012345數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第9頁。鄰接表的存儲(chǔ)表示表結(jié)點(diǎn)：typedefstructArcNode{intadjvex;//鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置structArcNode*nextarc;//鏈域，指示下一條邊或弧}ArcNode;adjvexnextarc頭結(jié)點(diǎn)：typedefstructVNode{vertextypedata;//存放頂點(diǎn)信息intindegree;//存放頂點(diǎn)的度ArcNode*firstarc;//指示第一個(gè)鄰接點(diǎn)}Vnode,AdjList[MAX_VERTEX_NUM];datafirstarc鄰接表存儲(chǔ)結(jié)構(gòu)：typedefstruct{

AdjListvertices;//表頭向量

intvernum,arcnum;//頂點(diǎn)數(shù)和弧數(shù)

}ALGraph;數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第10頁。

scanf(&G.vexnum,&G.arcnum)；

//輸入頂點(diǎn)數(shù)、邊數(shù)

for(i=0;i<G.vexnum;++i)

//構(gòu)造頂點(diǎn)數(shù)組

{scanf(&G.vertices[i].data)；

G.vertices[i].indegree=0;G.vertices[i].firstarc=NULL;}for(k=0;k<G.arcnum;++k)

//輸入各邊，構(gòu)造鄰接表

{scanf(&v1,&v2)；

//輸入一條邊依附的頂點(diǎn)(弧尾、弧頭)及權(quán)值

i=LocateVex(G,v1)；

//確定v1和v2在G中位置

j=LocateVex(G,v2)；

G.vertices[j].indegree++;

s=(*ArcNode)malloc(sizeof(ArcNode))

//申請(qǐng)表結(jié)點(diǎn)

s->adjvex=j;//插入（逆差）鏈表G.vertices[i]

s->nextarc=G.vertices[i].firstarc;

G.vertices[i].firstarc=s;}構(gòu)造有向圖的算法（鄰接表存儲(chǔ)結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第11頁。Statustopologicalsort(algraphG){initstack(s);

for(i=0;i<G.vexnum;++i)//入度為0的頂點(diǎn)入棧

if(indegree[i]==0)push(s,i);count=0;while(!stackempty(s)){pop(s,i);printf(i.vextices[i].data);++count;//對(duì)輸出頂點(diǎn)計(jì)數(shù)

for(p=G.vextices[i].firstarc;p;p=p->nextarc)//對(duì)鄰接點(diǎn)的入度減1{k=p->adjvex;//為0入棧，相當(dāng)于刪

if(!(--indegree[k]))push(s,k);}//除頂點(diǎn)的弧

}if(count<G.vexnum)returnERROR;elsereturnOK;}拓?fù)渑判蛩惴〝?shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第12頁。1．AOE網(wǎng)(邊表示活動(dòng)的網(wǎng))AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖。7.5

有向無環(huán)圖及其應(yīng)用三、關(guān)鍵路徑

其中:頂點(diǎn)表示事件(Event)，表明它的入邊的活動(dòng)已經(jīng)完成，它的出邊活動(dòng)可以開始的一種狀態(tài)，

弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間。通常將入度為零的點(diǎn)稱作源點(diǎn)；出度為零的點(diǎn)叫匯點(diǎn)。利用AOE網(wǎng)來估算工程的完成時(shí)間。數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第13頁。例設(shè)一個(gè)工程有4項(xiàng)活動(dòng)，4個(gè)事件事件V1——表示整個(gè)工程開始事件V4——表示整個(gè)工程結(jié)束問題：（1）完成整項(xiàng)工程至少需要多少時(shí)間(最短時(shí)間)？（2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？7.5

有向無環(huán)圖及其應(yīng)用三、關(guān)鍵路徑問題提出v2v4v1v3a1=3a2=4a3=2a4=3數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第14頁。

7.5

有向無環(huán)圖及其應(yīng)用三、關(guān)鍵路徑定義路徑長(zhǎng)度——路徑上各活動(dòng)持續(xù)時(shí)間之和關(guān)鍵路徑——路徑長(zhǎng)度最長(zhǎng)的路徑叫關(guān)鍵路徑Ve(j)——表示事件Vj的最早發(fā)生時(shí)間Vl(j)——表示事件Vj的最遲發(fā)生時(shí)間e(i)——表示活動(dòng)ai的最早開始時(shí)間l(i)——表示活動(dòng)ai的最遲開始時(shí)間l(i)-e(i)——表示完成活動(dòng)ai的時(shí)間余量關(guān)鍵活動(dòng)——關(guān)鍵路徑上的活動(dòng)，即l(i)=e(i)的活動(dòng)數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第15頁。如何找e(i)=l(i)的關(guān)鍵活動(dòng)？

設(shè)活動(dòng)ai用弧<j,k>表示，其持續(xù)時(shí)間記為：dut(<j,k>)則有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut(<j,k>)jkai7.5

有向無環(huán)圖及其應(yīng)用三、關(guān)鍵路徑2.問題分析數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第16頁。如何求Ve(j)和Vl(j)？(1)從Ve(源點(diǎn))=0開始向前遞推(拓?fù)湫蛄?7.5

有向無環(huán)圖及其應(yīng)用三、關(guān)鍵路徑2.問題分析vi1vjvi3vi2(2)從Vl(匯點(diǎn))=Ve(匯點(diǎn))開始向后遞推(逆拓?fù)湫蛄?Vj1vivj3Vj2數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第17頁。3.求關(guān)鍵路徑的算法a.輸入e條弧<j,k>，建立AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)(采用鄰接表)；b.從源點(diǎn)出發(fā)，令ve[源點(diǎn)]=0,按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間ve[i](2≤i≤n)。若網(wǎng)中有回路，則終止算法；c.從匯點(diǎn)出發(fā)，令vl[匯點(diǎn)]=ve[匯點(diǎn)]，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vl[i](n-1≥i≥1)；d.根據(jù)ve和vl的值，求出各活動(dòng)ai的最早開始時(shí)間e(i)和最遲開始時(shí)間l(i),若e(i)=l(i)，則ai是關(guān)鍵活動(dòng)。7.5

有向無環(huán)圖及其應(yīng)用三、關(guān)鍵路徑數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第18頁。7.5

有向無環(huán)圖及其應(yīng)用v9v8v7v6v4v5v3v2v1a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)ell-e00002266046258377077071031616014140033三、關(guān)鍵路徑例關(guān)鍵路徑：(v1,v2,v5,v7,v9)(v1,v2,v5,v8,v9)數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第19頁。7.6最短路徑一、問題的提出二、從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑三、每一對(duì)頂點(diǎn)之間的最短路徑數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第20頁。一、問題的提出7.6

最短路徑用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中：頂點(diǎn)——表示城市邊——表示城市間的交通聯(lián)系權(quán)——表示此線路的長(zhǎng)度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑——最短路徑數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第21頁。7.6

最短路徑8長(zhǎng)度最短路徑<V0,V2><V0,V1><V0,V2,V3><V0,V2,V3,V4><V0,V2,V3,V4,V5><V0,V1,V6>1313192120二、從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑516432085623013717329例又稱單源最短路徑。1．源點(diǎn)：路徑上的第一個(gè)頂點(diǎn)，起始點(diǎn)。2．終點(diǎn)：最后一個(gè)頂點(diǎn)。3．單源最短路徑：給定有向圖G和源點(diǎn)v，求v到G中其余各頂點(diǎn)的最短路徑。數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第22頁。4.迪杰斯特拉(Dijkstra)算法基本思想按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法。用帶權(quán)的鄰接矩陣arcs來表示帶權(quán)有向圖，arcs[i][j]表示弧<vi,vj>上的權(quán)值。(1)引入一個(gè)輔助向量D,D[i]表示當(dāng)前所找到的源點(diǎn)v到每個(gè)終點(diǎn)vi的最短路徑長(zhǎng)度。設(shè)一個(gè)S集合存放已確定最短路徑長(zhǎng)度的頂點(diǎn)。初始狀態(tài)：S集為空集；若v到vi有弧，則D[i]為v到vi弧上的權(quán)值；否則，D[i]為∞。

最短路徑的初值即為弧的權(quán)值：

D[i]=arcs[LocateVex(G,v)][i]vi∈V二、從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑7.6

最短路徑數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第23頁。(2)選擇vj，使得D[j]=min{D[i]|vi∈V-S}vj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)。vj進(jìn)入S集。(3)修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長(zhǎng)度，如果：D[j]+arcs[j][k]<D[k]則修改D[k]為：D[k]=D[j]+arcs[j][k]

即確定v→vk的當(dāng)前最短路徑,這個(gè)最短路徑可能是弧<v,vk>的權(quán)值D[k]，也可能是路徑(v,vj,vk)的路徑長(zhǎng)度。

(4)重復(fù)操作(2)、(3)n-1次。求得從v到圖上其余各頂點(diǎn)的最短路徑。二、從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑7.6

最短路徑數(shù)據(jù)結(jié)構(gòu)-第七章-圖7全文共26頁，當(dāng)前為第24頁。13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1>--