最小生成樹
最短路徑
拓?fù)渑判?br>
關(guān)鍵路徑
最小生成樹
?一個(gè)圖可以有許多棵不同的生成樹
?所有生成樹具有以下共同特點(diǎn)
生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同;
生成樹是圖的極小連通子圖，去掉一條邊則非連通;
一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊;
在生成樹中再加一條邊必然形成回路。
?含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹。
設(shè)圖G=(V, E)是個(gè)連通圖，當(dāng)從圖任一頂點(diǎn)出發(fā)遍歷圖G 時(shí)，將邊集E(G)分成兩個(gè)集合T(G)和B(G)。其中T(G)是遍歷圖時(shí)所經(jīng)過的邊的集合，B(G) 是遍歷圖時(shí)未經(jīng)過的邊的集合。顯然，G1(V,T) 是圖G的極小連通子圖。即子圖G1是連通圖G的生成樹。
最小生成樹
最小生成樹:給定- -個(gè)無向網(wǎng)絡(luò)，在該網(wǎng)的所有生成樹中，使得各邊權(quán)值之和最小的那棵生成樹稱為該網(wǎng)的最小生成樹，也叫最小代價(jià)生成樹。
構(gòu)造最小生成樹
構(gòu)造最小生成樹Minimum Spanning Tree
構(gòu)造最小生成樹的算法很多,其中多數(shù)算法都利用了MST的性質(zhì)。
MST性質(zhì):設(shè)N= (V, E)是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若邊(u,v)是一條具有最小權(quán)值的邊，其中u∈U, v∈V-U,則必存在一棵包含邊(u, v)的最小生成樹。
構(gòu)造最小生成樹方法一-: 普里姆(Prim)算法
算法思想:
?設(shè)N=(V, E)是連通網(wǎng)，TE是N上最小生成樹中邊的集合。
?初始令U={Uo}, (Ug∈V), TE={}。
?在所有ueU, VE V-U的邊(u, v∈E中，找一條代價(jià)最小的邊(Uo, v)。
?將(Uo, v)并入集合TE,同時(shí)v并入U(xiǎn)。
?重復(fù)上述操作直至U=V為止，則T=(V, TE) 為N的最小生成樹。
構(gòu)造最小生成樹方法二:克魯斯卡爾(Kruskal) 算法。
算法思想:
設(shè)連通網(wǎng)N= (V E),令最小生成樹初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V {}),每個(gè)頂點(diǎn)自成一個(gè)連通分量。
?在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上(即:不能形成環(huán)) ,則將此邊加入到T中;否則，舍去此邊，選取下一條代價(jià)最小的邊。依此類推，直至T中所有頂點(diǎn)都在同一連通分量.上為止。
最短路徑
問題抽象:在有向網(wǎng)中A點(diǎn)(源點(diǎn))到達(dá)B點(diǎn)(終點(diǎn))的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。最短路徑與最小生成樹不同，路徑上不一定包含n個(gè)頂點(diǎn)，也不一定包含n- 1條邊。
兩種常見的最短路徑問題:
一、單源最短路徑一 用Diikstra (迪杰斯特拉)算法
二、所有頂點(diǎn)間的最短路徑一-用Floyd (弗洛伊德)算法
Dijistra算法
1.初始化:先找出從源點(diǎn)v。到各終點(diǎn)vk的直達(dá)路徑(Vo,Vk) ,即通過一條弧到達(dá)的路徑。
2.選擇:從這些路徑中找出一條長度最短的路徑(Vo,u) 。
3.更新:然后對(duì)其余各條路徑進(jìn)行適當(dāng)調(diào)整:
若在圖中存在弧(u,vk) ，且(Vo,u) + (u,Vk) < (Vo,vk) ，則以路徑(Vo,U,Vk) 代替(Vo,Vk) 。
在調(diào)整后的各條路徑中，再找長度最短的路徑，依此類推。
迪杰斯特拉(Dijkstra)算法:按路徑長度遞增次序產(chǎn)生最短路徑
1、把V分成兩組:
(1) S:已求出最短路徑的頂點(diǎn)的集合。
(2) T=V -S :尚未確定最短路徑的頂點(diǎn)集合。
2、將T中頂點(diǎn)按最短路徑遞增的次序加入到S中
保證: (1) 從源點(diǎn)V到S中各頂點(diǎn)的最短路徑長度都不大于從Vo到T中任何頂點(diǎn)的最短路徑長度。
(2)每個(gè)頂點(diǎn)對(duì)應(yīng)一-個(gè)距離值:S中頂點(diǎn):從Vo到此頂點(diǎn)的最短路徑長度。T中頂點(diǎn):從Vo到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長度。
Dijkstra算法步驟:
初始時(shí)令S={Vo}, T={其余頂點(diǎn)}。T中頂點(diǎn)對(duì)應(yīng)的距離值用輔助數(shù)組D存放。D[]初值:若<V, V;> 存在，則為其權(quán)值;否則為∞。從T中選取一個(gè)其距離值最小的頂點(diǎn)V;加入S。對(duì)T中頂點(diǎn)的距離值進(jìn)行修改:若加進(jìn)v;作中間頂點(diǎn)，從V到V;的距離值比不加V;的路徑要短，則修改此距離值。重復(fù)上述步驟，直到S = V為止。
拓?fù)渑判?amp;關(guān)鍵路徑
有向無環(huán)圖簡稱DAG圖Direction Cyclical Grapt
有向無環(huán)圖常用來描述一個(gè)工程或系統(tǒng)的進(jìn)行過程。(通常把計(jì)劃施工、生產(chǎn)、程序流程等當(dāng)成是一個(gè)工程)
一個(gè)工程可以分為若干個(gè)子工程，只要完成了這些子工程(活動(dòng))就可以導(dǎo)致整個(gè)工程的完成。
AOV網(wǎng)（解決拓?fù)渑判颍?
用一-個(gè)有向圖表示一-個(gè)工程的各子工程及其相互制約的關(guān)系，其中以頂點(diǎn)表示活動(dòng)，弧表示活動(dòng)之間的優(yōu)先制約關(guān)系，稱這種有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)，簡稱AOV網(wǎng)(Activity On Vertex network)。
AOV網(wǎng)的特點(diǎn):
1、若從i到j(luò)有一條有向路徑，則i是j的前驅(qū);j是i 的后繼。
2、若< i,j>是網(wǎng)中有向邊，則i是j的直接前驅(qū);j是 i的直接后繼。
3、AOV 網(wǎng)中不允許有回路,因?yàn)槿绻谢芈反嬖?，則表明某項(xiàng)活動(dòng)以自己為先決條件，顯然這是荒謬的。
拓?fù)渑判?/h5>
在AOV網(wǎng)沒有回路的前提下，我們將全部活動(dòng)排列成一個(gè)線性序列，使得若AOV網(wǎng)中有弧<i, j>存在，則在這個(gè)序列中，i 一定排在j的前面，具有這種性質(zhì)的線性序列稱為拓?fù)溆行蛐蛄?，相?yīng)的拓?fù)溆行蚺判虻乃惴ǚQ為拓?fù)渑判颉?/p>
拓?fù)渑判虻姆椒?
1、在有向圖中選一一個(gè)沒有 前驅(qū)的頂點(diǎn)且輸出之。
2、從圖中刪除該頂點(diǎn)和所有以它為尾的弧。
3、重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出;或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止
拓?fù)湫蛄?
C1,C2, C3,C4, C5, C7, C9, C10, C11,C6, C12, C8
C9, C10, C11, C6, C1, C12, C4, C2,C3, C5, C7, C8
一 個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ?的
拓?fù)渑判虻囊粋€(gè)重要應(yīng)用:
檢測AOV網(wǎng)中是否存在環(huán)方法:
對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)。
AOE網(wǎng)（解決關(guān)鍵路徑）:
用一個(gè)有向圖表示一個(gè)工程的各子工程及其相互制約的關(guān)系，以弧表示活動(dòng)，以頂點(diǎn)表示活動(dòng)的開始或結(jié)束事件，稱這種有向圖為邊表示活動(dòng)的網(wǎng)，簡稱為AOE網(wǎng)(Activity On Edge) 。
關(guān)鍵路徑
把工程計(jì)劃表示為邊表示活動(dòng)的網(wǎng)絡(luò)，即AOE網(wǎng)，用頂點(diǎn)表示事件，弧表示活動(dòng)，弧的權(quán)表示活動(dòng)持續(xù)時(shí)間。
事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開始。
對(duì)于AOE網(wǎng)，我們關(guān)心兩個(gè)問題:
(1)完成整項(xiàng)工程至少需要多少時(shí)間?
(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵?
關(guān)鍵路徑一路徑長度最長的路徑。
路徑長度一路徑 上各活動(dòng)持續(xù)時(shí)間之和。
求關(guān)鍵路徑步驟:
1.求ve(i)、 vl(j)
2.求e(i)、 l(i)
3.計(jì)算|(i)-e(i)
