【正文】 ()) { (x)。 u=()。 v=()。 if (u!=v){ (u,v)。 k++。 cout(, ,) 。 } } coutendl。 if (kn2) throw NonConnected。 } 克魯斯卡爾算法的時間復(fù)雜度為 O（ elog e） 。 算法正確性 定理 6－ 5 設(shè)圖 G=（ V， E） 是一個帶權(quán)連通圖 ， U是 V的一個真子集 。 若邊 (u,v)?E是所有 u?U, v?VU的邊中權(quán)值最小者 ， 那么一定存在 G的一棵最小代價生成樹 T=(V,S)， (u,v)?S。 這一性質(zhì)稱為 MST（ minimum spanning tree） 性質(zhì) 。 定理 6－ 6 普里姆算法和克魯斯卡爾算法都將產(chǎn)生一個帶權(quán)無向連通圖的最小代價生成樹 。 問題描述 單源最短路徑問題是：給定帶權(quán)的有向圖G=(V,E)和圖中結(jié)點(diǎn) s?V，求從 s到其余各結(jié)點(diǎn)的最短路徑，其中， s稱為源點(diǎn)。 單源最短路徑 貪心法求解 迪杰斯特拉 （ Dijkstra） 算法 首先求得長度最短的一條最短路徑 ， 再求得長度次短的一條最短路徑 ， 依此類推 ， 直到從源點(diǎn)到其它所有結(jié)點(diǎn)之間的最短路徑都已求得為止 。 迪杰斯特拉算法 【 程序 6－ 10】 迪杰斯特拉算法 templateclass T class MGraph { public: MGraph(int mSize)。 void Dijkstra(int s,T*amp。 d,int*amp。 path)。 …… private: int Choose(int* d, bool* s)。 …… T**a。 int n。 }。 template class T int MGraphT::Choose(int* d, bool* s) { int i,minpos。 T min。 min=INFTY。 minpos=1。 for (i=1。in。i++) if (d[i]min amp。amp。!s[i]){ min=d[i]。minpos=i。 } return minpos。 } template class T void MGraphT::Dijkstra(int s, T*amp。 d,int*amp。 path) { int k,i,j。 if (s0||sn1) throw OutOfBounds。 bool *inS=new bool[n]。 d=new T[n]。path=new int[n]。 for (i=0。in。i++){ inS[i]=false。d[i]=a[s][i]。 if (i!=s amp。amp。 d[i]INFTY) path[i]=s。 else path[i]=1。 } inS[s]=true。 d[s]=0。 for (i=1。in1。i++){ k=Choose(d,inS)。 inS[k]=true。 for (j=0。 jn。 j++) if (!inS[j] amp。amp。 d[k]+a[k][j] d[j]){ d[j]=d[k]+a[k][j]。 path[j]=k。 } } } 算法正確性 定理 6－ 7 已知帶權(quán)有向圖 G=(V,E)， 其源點(diǎn)為 s， 迪杰斯特拉算法使得對所有 i， i?V{s}， d[i]??(s,i)， 且一旦d[i]= ?(s,i)， 它將不再改變 。 定理 6－ 8 已知帶權(quán)有向圖 G=(V,E)， 其源點(diǎn)為 s， 迪杰斯特拉算法使得對所有結(jié)點(diǎn) i和 j, i?S， j?VS， 必有d[i]?d[j]。 定理 6－ 9 已知帶非負(fù)權(quán)值的有向圖 G=(V,E)， 路徑 （ s=v0, ? ,vi,? vk=t） 是從 s到 vk的一條最短路徑 ， vi?V，0?i?kn， 則子路徑 （ s=v0, ? ,vi） 和 （ vi,? vk=t） 必定分別是從 s到 vi 和 vi到 t的最短路徑 。 定理 6－ 10 已知帶非負(fù)權(quán)值的有向圖 G=(V,E)， 其源點(diǎn)為 s， 迪杰 斯 特 拉 算 法 結(jié) 束 時 ， 對 所 有 結(jié) 點(diǎn) i ， 有d[i]=?(s,i)。 單帶最優(yōu)存儲 問題 設(shè)有 n個程序編號為 0,… ,n1， 存放在長度為 L的磁帶上 ， 程序 i在磁帶上的存儲長度為 ai， 0?in。 假定每個程序被檢索地概率相等 ， 則 平均檢索時間 （ mean retrieval time MRT） 定義為 單帶最優(yōu)存儲問題是求這 n個程序的一種排列 ， 使得 MRT有最小值 。 ???1n0kktn1 磁帶最優(yōu)存儲 例 6－ 5 設(shè) n=3， (a0,a1,a2)=(5,10,3)。 貪心法求解 量度標(biāo)準(zhǔn)：計算迄今為止已選的那部分程序的 D值 ，選擇下一個程序應(yīng)使得該值增加最小 。 ?定理 6－ 11 設(shè)有 n個程序 {0,1,… ,n1}, 程序 i的長度為 ai， 0?in，且有 a0?a1?? ?an?1， ?=(?0,?1,… ,?n?1)是這 n個作業(yè)的一種排列 。 那么只有當(dāng) ?j=j， 0?in時 ， D(?)=有最小值 。 多帶最優(yōu)存儲 問題 設(shè)有 m1條磁帶 T0,T1,… ,Tm?1和 n個程序 。 要求將此n個程序分配到這 m條磁帶上 ， 令 Ij,0?jm 是存放在第 j條磁帶上的程序子集的某種排列 ， D(Ij) 的定義如前面相同 ， 那么 ， 求 m條磁帶上檢索一個程序的平均檢索時間的最小值等價于求 的最小值 。 ??? mj0j )D ( I 【 程序 6－ 11】 多帶最優(yōu)存儲 include void Store(int n, int m) { int j = 0。 for (int i=0。 in。 i++) { cout 將程序 i 加到磁帶 jendl。 j=(j+1)% m。 } coutendl。 } 定理 6－ 12 設(shè)有 n個程序 {0,1,… ,n1}, 程序 i的長度為 ai， 0?in，且有 a0?a1?… ?an?1， 程序 6－ 11 實(shí)現(xiàn)將 n個程序分配到 m條磁帶上 ， 且有最小 TD值 。 最優(yōu)量度標(biāo)準(zhǔn) 選擇最優(yōu)量度標(biāo)準(zhǔn)是使用貪心法求解問題的核心問題 。 貪心算法每一步作出的選擇可以依賴以前作出的選擇 ， 但不依賴將來的選擇 ， 也不依賴于子問題的解 。 對于一個貪心算法 ， 必須證明所采用的量度標(biāo)準(zhǔn)能夠?qū)е乱粋€整體最優(yōu)解 。 貪心法的基本要素 最優(yōu)子結(jié)構(gòu) 最優(yōu)子結(jié)構(gòu)特性是關(guān)于問題最優(yōu)解的特性 。 當(dāng)一個問題的最優(yōu)解中包含了子問題的最優(yōu)解 ， 則稱該問題具有 最優(yōu)子結(jié)構(gòu)特性 （ optimal substructure） 。 一般而言 ， 如果一個最優(yōu)化問題的解結(jié)構(gòu)具有元組形式 ， 并具有最優(yōu)子結(jié)構(gòu)特性 ， 我們可以嘗試選擇量度標(biāo)準(zhǔn) 。