中南大學(xué)204算法試卷及答案分析報(bào)告

1、中南大學(xué)考試試卷2013 - 2014 學(xué)年 下 學(xué)期 時(shí)間100分鐘2014 年6月6日算法分析與設(shè)計(jì) 課程48學(xué)時(shí)丄學(xué)分 考試形式：閉 卷專業(yè)年級(jí)：12級(jí)計(jì)算機(jī)、信安、物聯(lián)本科生，總分 100分，占總評(píng)成績(jī)70 %注：此頁(yè)不作答題紙，請(qǐng)將答案寫在答題紙上一、簡(jiǎn)答題（本題30分，每小題5分）1、陳述算法在最壞情況下的時(shí)間復(fù)雜度和平均時(shí)間復(fù)雜度；這兩種評(píng)估算法復(fù)雜性的方 法各自有什么實(shí)際意義？1 最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般不特別說(shuō)明，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度。意義：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何

2、更長(zhǎng)2 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下，算法的期望運(yùn)行時(shí)間。意義：在輸入不同的情況下算法的運(yùn)行時(shí)間復(fù)雜度可能會(huì)發(fā)生變化。平均時(shí)間復(fù)雜度給出了算法的期望運(yùn)行時(shí)間，有助于算法好壞的評(píng)價(jià)以及在不同算法 之間比較時(shí)有一個(gè)統(tǒng)一標(biāo)準(zhǔn)2、簡(jiǎn)單描述分治法的基本思想。分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題相同。遞歸地解這些子問題，然后將各個(gè)子問題的解合并得到原問 題的解。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動(dòng)態(tài)規(guī)劃算法解決問題

3、提供了重要線索。4、何謂P、NR NPC問題P（Polynomial問題）：也即是多項(xiàng)式復(fù)雜程度的問題。NP就是Non-deterministicPolynomial的問題，也即是多項(xiàng)式復(fù)雜程度的非確定性問題。NPQNP Complete）問題，這種問題只有把解域里面的所有可能都窮舉了之后才能得出 答案，這樣的問題是 NP里面最難的問題，這種問題就是NPC問題。5、試比較回溯法與分支限界法。1、引言1.1回溯法回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問題的解。如果肯定不包含，則 跳過對(duì)該結(jié)點(diǎn)為根的子樹的搜索，逐層向

4、其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹，繼續(xù)按 深度優(yōu)先策略搜索。這種以深度優(yōu)先方式系統(tǒng)搜索問題解的算法稱為回溯法。1.2分支限界法分支限界法是以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹，在每一個(gè)活結(jié)點(diǎn)處，計(jì)算一個(gè)函數(shù)值，并根據(jù)函數(shù)值，從當(dāng)前活結(jié)點(diǎn)表中選擇一個(gè)最有利的結(jié)點(diǎn)作為擴(kuò) 展結(jié)點(diǎn)，使搜索朝著解空間上有最優(yōu)解的分支推進(jìn)，以便盡快地找出一個(gè)最優(yōu)解，這種 方法稱為分支限界法。2、回溯法的基本思想用回溯法解問題時(shí)，應(yīng)明確定義問題的解空間。問題的解空間至少應(yīng)包含問題的一 個(gè)解。之后還應(yīng)將解空間很好的組織起來(lái)，使得能用回溯法方便的搜索整個(gè)解空間。在 組織解空間時(shí)常用到兩種典型的解空間樹，即子集樹和排列樹

5、。確定了解空間的組織結(jié) 構(gòu)后，回溯法從開始結(jié)點(diǎn)出發(fā)，以深度優(yōu)先方式搜索整個(gè)解空間。這個(gè)開始結(jié)點(diǎn)成為活 結(jié)點(diǎn)，同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處，搜索向縱深方向移至一個(gè)新 結(jié)點(diǎn)。這個(gè)新結(jié)點(diǎn)就成為新的活結(jié)點(diǎn)，并成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處 不能再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)至最近的一 個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)?；厮莘ㄒ赃@種工作方式遞歸的在解 空間中搜索，直至找到所要求的解或解空間中已無(wú)活結(jié)點(diǎn)時(shí)為止。3、分支限界法的基本思想用分支限界法解問題時(shí)，同樣也應(yīng)明確定義問題的解空間。之后還應(yīng)將解空間很好 的組織起來(lái)。分支限界法也有兩種

6、組織解空間的方法，即隊(duì)列式分支限界法和優(yōu)先隊(duì)列 式分支限界法。兩者的區(qū)別在于：隊(duì)列式分支限界法按照隊(duì)列先進(jìn)先出的原則選取下一 個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)，而優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí) 最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。分支限界法常以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索問題的解空間樹。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)。活結(jié)點(diǎn) 一旦成為擴(kuò)展結(jié)點(diǎn)，就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解 或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn) 表中取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程。這個(gè)過程一直持續(xù)到找 到所需的

7、解或活結(jié)點(diǎn)表為空時(shí)為止。4、回溯法的設(shè)計(jì)原理在設(shè)計(jì)一個(gè)回溯算法時(shí)，通常按照以下步驟進(jìn)行：（1）針對(duì)所給問題，定義問題的解空間；（2）確定易于搜索的解空間結(jié)構(gòu)；（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無(wú)效搜索。在一般情況下用遞歸方法實(shí)現(xiàn)回溯法的基本框架如下：void backtrack （ int t ）if （ t>n ） output （ x）；elsefor （int i=f （n, t）； i<=g （ n, t）； i+） xt=h （i）；if(constraint(t) &&bound (t) backtrack (t+1 );其中：

8、t表示遞歸深度，output (x)記錄或輸出得到的可行解x, f (n, t )和g(n，t)分別表示在當(dāng)前擴(kuò)展結(jié)點(diǎn)處未搜索過的子樹的起始編號(hào)和終止編號(hào)，h (i )表示當(dāng)前擴(kuò)展結(jié)點(diǎn)處的第i個(gè)可選值，constraint(t )和bound (t)表示當(dāng)前擴(kuò)展結(jié)點(diǎn)的約束函數(shù)和限界函數(shù)。5、分支限界法的設(shè)計(jì)原理在設(shè)計(jì)一個(gè)分支限界算法時(shí)，通常按照以下步驟進(jìn)行：(1) 針對(duì)所給問題，定義問題的解空間；(2) 確定易于搜索的解空間結(jié)構(gòu)；(3) 以廣度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無(wú)效搜索。6、回溯法與分支限界法的差異及應(yīng)用回溯法與分支定界法都是在問題的解空間上搜索問題解的算法。但是

9、兩者是有區(qū)別的：首先，求解目標(biāo)不同：一般而言，回溯法的求解目標(biāo)是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標(biāo)則是盡快地找出滿足約束條件的一個(gè)解。其次，搜索方法不同：由于求解目標(biāo)不同，導(dǎo)致分支限界法與回溯法對(duì)解空間的搜索方式也不同，回溯法 采用深度優(yōu)先方法搜索解空間，而分支限界法一般采用用廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間。再次，對(duì)擴(kuò)展結(jié)點(diǎn)的擴(kuò)展方式不同：在搜索解空間書中兩者的主要區(qū)別在于它們對(duì)當(dāng)前擴(kuò)展結(jié)點(diǎn)所采用的擴(kuò)展方式不同。在回溯法中，如果當(dāng)前的擴(kuò)展結(jié)點(diǎn)不能夠再向縱深方向移動(dòng)，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成 為死結(jié)點(diǎn)，此時(shí)應(yīng)回溯到最近的一個(gè)活結(jié)點(diǎn)處，并使此活結(jié)點(diǎn)成為擴(kuò)展結(jié)點(diǎn)。而在分支

10、 限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)，就一 次性產(chǎn)生其所有兒子結(jié)點(diǎn)。最后，存儲(chǔ)空間的要求不同：分支限界法的存儲(chǔ)空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。下面結(jié)合具體的實(shí)例來(lái)說(shuō)明何種情況下比較適合采用回溯法，何種情況下比較適合采用分支限界法：適合采用回溯法的問題：最典型的代表如n后問題，即在n*n個(gè)格的棋盤上放置彼此不受攻擊的n個(gè)皇后。按照國(guó)際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列 或同一斜線上的棋子。對(duì)于n后問題，解與解之間不存在優(yōu)劣的區(qū)別。必須要搜索到葉節(jié)點(diǎn)時(shí)才能確定出一組解。這種情況下，我們采用回溯法來(lái)解決時(shí)，采用排列樹的

11、解空 間結(jié)構(gòu)，在最壞的情況下，其堆棧的深度不會(huì)超過n。而采用分支限界法時(shí)，由于解之間不存在優(yōu)劣關(guān)系，故不可能用限界函數(shù)剪枝，需要較大的存儲(chǔ)空間。適合采用分支限界法的問題：最典型的代表如布線問題，即印刷電路板將布線區(qū)域戈U分成n*m個(gè)方格陣列。要求確定連接方格a的中點(diǎn)到方格b的中點(diǎn)的最短布線方案。在布線時(shí)，電路只能沿直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖 標(biāo)記，其他線路不允許穿過被封鎖的方格。此問題，如果采用回溯法來(lái)解決時(shí)，為了找 到最短路徑，必須把整個(gè)區(qū)域的所有路徑逐一搜索后才能得到最優(yōu)解，這使得算法效率 較低。而如果用分支限界法來(lái)解決，則可以保證找到的解是最短的布線方案，因

12、為如果 存在一條由a至b的更短的路徑，b結(jié)點(diǎn)一定會(huì)更早地被加入到活結(jié)點(diǎn)隊(duì)列中并得到處 理。6、貪心法是一種通過多步選擇，試圖獲得最優(yōu)解的方法。貪心法每次選擇的原則是什么？ 請(qǐng)舉例說(shuō)明。設(shè)計(jì)貪心算法的三個(gè)步驟將最優(yōu)化問題轉(zhuǎn)化為這樣的形式：對(duì)其做出一次選擇后，只剩下一個(gè)子問題需要求解（比較重要的一步）證明作出貪心選擇后，原問題總是存在最優(yōu)解，即貪心選擇總是安全的證明作出貪心選擇后，剩余的子問題滿足性質(zhì)：其最優(yōu)解與貪心選擇組合即可得 到原問題的最優(yōu)解，這樣就得到了最優(yōu)子結(jié)構(gòu)兩個(gè)關(guān)鍵因素1. 貪心選擇性質(zhì)：可以通過做出局部最優(yōu)（貪心）選擇來(lái)構(gòu)造全局最優(yōu)解；即每個(gè)步驟做出貪心選擇能生成全局最優(yōu)解【視不同

13、具體問題進(jìn)行證明，沒有普遍適用的方法】2. 最優(yōu)子結(jié)構(gòu)：一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解經(jīng)典最優(yōu)化問題的兩個(gè)變形0-1背包問題：一個(gè)正在搶劫的小偷發(fā)現(xiàn)了n個(gè)商品，第i個(gè)商品價(jià)值vi美元，重wi磅，vi和wi都是整數(shù)；小偷想盡可能拿走價(jià)值更多的商品，但是他的背包最多能容納W磅的商品，W是一個(gè)整數(shù)【對(duì)每個(gè)商品，不能拿走一部分，要么完整拿走，要么留下） 分?jǐn)?shù)背包問題：條件和0-1背包問題一樣，但對(duì)每個(gè)商品，小偷可以拿走一部分兩個(gè)問題都有最優(yōu)子結(jié)構(gòu)，很相似，但是貪心算法可以求解分?jǐn)?shù)背包問題，而不能求解0-1背包問題分?jǐn)?shù)背包問題：計(jì)算每個(gè)商品的每磅價(jià)值vi/wi，每次選擇每磅價(jià)值最高的商品即可0-1

14、背包問題：因?yàn)樾⊥禑o(wú)法裝滿背包，空閑空間降低了方案的有效每磅價(jià)值； 當(dāng)我們考慮一個(gè)商品食肉裝入背包，需要比較包含此商品的子問題的解和不包含它的子問題的解，然后才能做出選擇當(dāng)然，由于兩個(gè)問題都有最優(yōu)子結(jié)構(gòu)，所以能用動(dòng)態(tài)規(guī)劃算法進(jìn)行求解。/拓展/二、簡(jiǎn)答題(本題 25分，每小題5分)1、簡(jiǎn)單描述分治法的基本思想。2、簡(jiǎn)述動(dòng)態(tài)規(guī)劃方法所運(yùn)用的最優(yōu)化原理。3、何謂最優(yōu)子結(jié)構(gòu)性質(zhì)？4、簡(jiǎn)單描述回溯法基本思想。5、何謂P、NP NPC'可題二、簡(jiǎn)答題(本題 25分，每小題5分)1、分治法的基本思想 是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題， 這些子 問題互相獨(dú)立且與原問題相同；對(duì)這 k個(gè)子

15、問題分別求解。如果子問題的規(guī)模仍然 不夠小，則再劃分為 k個(gè)子問題，如此遞歸的進(jìn)行下去，直到問題規(guī)模足夠小，很 容易求出其解為止；將求出的小規(guī)模的問題的解合并為一個(gè)更大規(guī)模的問題的解， 自底向上逐步求出原來(lái)問題的解。2、“最優(yōu)化原理”用數(shù)學(xué)化的語(yǔ)言來(lái)描述：假設(shè)為了解決某一優(yōu)化問題，需要依次作出n個(gè)決策D1, D2,，Dn,如若這個(gè)決策序列是最優(yōu)的，對(duì)于任何一個(gè)整數(shù)k, 1 < k<n，不論前面k個(gè)決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所確定的當(dāng) 前狀態(tài)，即以后的決策 Dk+1, Dk+2,，Dn也是最優(yōu)的。3、 某個(gè)問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)

16、性質(zhì)。4、回溯法的基本思想 是在一棵含有問題全部可能解的狀態(tài)空間樹上進(jìn)行深度優(yōu)先搜索，解為葉子結(jié)點(diǎn)。搜索過程中，每到達(dá)一個(gè)結(jié)點(diǎn)時(shí)，則判斷該結(jié)點(diǎn)為根的子樹是否含有問題的解，如果可以確定該子樹中不含有問題的解，則放棄對(duì)該子樹的搜索，退回到 上層父結(jié)點(diǎn)，繼續(xù)下一步深度優(yōu)先搜索過程。在回溯法中，并不是先構(gòu)造出整棵狀態(tài) 空間樹，再進(jìn)行搜索，而是在搜索過程，逐步構(gòu)造出狀態(tài)空間樹，即邊搜索，邊構(gòu)造。5、P(Polynomial問題)：也即是多項(xiàng)式復(fù)雜程度的問題。NP就是Non-deterministicPolynomial的問題，也即是多項(xiàng)式復(fù)雜程度的非確定性問題。NPC(NP Complete)問題，這種

17、問題只有把解域里面的所有可能都窮舉了之后才能得出 答案，這樣的問題是NP里面最難的問題，這種問題就是NPC問題。/二、選擇題(14分，每題2分)1. 下述表達(dá)不正確的是 。A. n2/2 + 2 n的漸進(jìn)表達(dá)式上界函數(shù)是0(2)B . n2/2 + 2 n的漸進(jìn)表達(dá)式下界函數(shù)是Q(2 n)C. logn3的漸進(jìn)表達(dá)式上界函數(shù)是O(logn) D . logn3的漸進(jìn)表達(dá)式下界函數(shù)是Q(n 3)logn 3的漸進(jìn)表達(dá)式下界函數(shù)是O（logn）2. 下列算法中通常以自底向上的方式求解最優(yōu)解的是 A.動(dòng)態(tài)規(guī)劃法B.貪心法C.回溯法3. 下面關(guān)于NP問題說(shuō)法正確的是A. NP問題都是不可能解決的問題B

18、. P類問題包含在 NP類問題中B. NP完全問題是P類問題的子集D. NP 類問題包含在 P類問題中首先這些p和 叩都是用來(lái)描述解決一個(gè)問題需要的時(shí)間和它輸入規(guī)模之間的關(guān)系P問題：一個(gè)問題可以在多項(xiàng)式（0（門你）的時(shí)間復(fù)雜度內(nèi)解決例如：n個(gè)數(shù)的排序（不超過 0（nA2）NP問題：一個(gè)問題的解可以在多項(xiàng)式的時(shí)間內(nèi)被證實(shí)或證偽例如：典型的子集求和問題，給定一個(gè)整數(shù)集合求是否存在一個(gè)非空子集它的和為零。 如給定集合s=-1,3,2,-5,6，很明顯子集32-5能滿足問題，并且驗(yàn)證該解只需要 線性時(shí)間復(fù)雜度就能被證實(shí)。NP-hard 問題：任意np問題都可以在多項(xiàng)式時(shí)間內(nèi)歸約為該問題。歸約的意思是為

19、了解決問題 A,先將問題A歸約為另一個(gè)問題B,解決問題B同時(shí)也間接解決了問題 A。例如，停機(jī)問題。NPC'可題：既是NP問題，也是 NP-hard問題。例如，SAT問題（第一個(gè)NPC問題）。該問題的基本意思是，給定一系列布爾變量以及 它的約束集，是否存在一個(gè)解使得它的輸出為真。相互關(guān)系：顯然，所有P問題都是NP問題，反之則不一定。npc問題是np問題的子集，也是p問 題和np問題的差異所在。如果找到一個(gè)多項(xiàng)式內(nèi)能被解決的npc問題的解決方法，那么 P=NP4. 下列算法中不能解決 0/1背包問題的是A.貪心法B.動(dòng)態(tài)規(guī)劃C.回溯法D.分支限界法5. 是貪心算法與動(dòng)態(tài)規(guī)劃算法的共同點(diǎn)。A

20、.重疊子問題 B .構(gòu)造最優(yōu)解 C .貪心選擇性質(zhì)D.最優(yōu)子結(jié)構(gòu)性質(zhì)貪心算法的基本要素貪心算法通過一系列的選擇得到問題的解。它所做出的每一選擇都是當(dāng)前狀態(tài)下局部最好選擇，即貪心選擇?？梢杂秘澬乃惴ㄇ蠼獾膯栴}一般具有兩個(gè)重要性質(zhì)：(1) 貪心選擇性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解能通過一系列局部 最優(yōu)的選擇(即貪心選擇)來(lái)達(dá)到。(2) 最優(yōu)子結(jié)構(gòu)性質(zhì)。與動(dòng)態(tài)規(guī)劃算法相同，最優(yōu)子結(jié)構(gòu)性質(zhì)是一個(gè)問題可用貪心算法求解的關(guān)鍵特征。6. 以下關(guān)于判定問題難易處理的敘述中正確的是 。A. 可以由多項(xiàng)式時(shí)間算法求解的問題是難處理的B. 需要超過多項(xiàng)式時(shí)間算法求解的問題是易處理的C可以由多項(xiàng)式時(shí)間算

21、法求解的問題是易處理的D.需要超過多項(xiàng)式時(shí)間算法求解的問題是不能處理的7. n個(gè)同學(xué)拎著水桶在一個(gè)水龍頭前面排隊(duì)打水，水桶有大有小，水桶必須打滿水，水流恒定。如下說(shuō)法不正確？A. 讓水桶大的人先打水，可以使得每個(gè)人排隊(duì)時(shí)間之和最小B. 讓水桶小的人先打水，可以使得每個(gè)人排隊(duì)時(shí)間之和最小C. 讓水桶小的人先打水，在某個(gè)確定的時(shí)間t內(nèi)，可以讓盡可能多的人打上水D. 若要在盡可能短的時(shí)間內(nèi)，n個(gè)人都打完水，按照什么順序其實(shí)都一樣三、解答題(30分)1. 用貪心法求下圖的最大生成樹 (5分)8貪心算法最小生成樹設(shè)G = (V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中的每一條邊(v,w)的權(quán)為cvw。如果

22、G的子圖G'是一棵包含 G的所有頂點(diǎn)的樹，則稱G為G的生成樹。生成樹上各邊權(quán)的總和稱為生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。構(gòu)造最小生成樹的兩種方法：Prim算法和Kruskal算法。、最小生成樹的性質(zhì)設(shè)G =(V,E)是連通帶權(quán)圖，這樣的邊中，(u,v)的權(quán)cuv 中一條邊。這個(gè)性質(zhì)有時(shí)也稱為U是V的真子集。如果(u,v) E,且u U,v V-U,且在所有 最小，那么一定存在 G的一棵最小生成樹，它意(u,v)為其MST性質(zhì)。二、Prim算法設(shè)G = (V,E)是連通帶權(quán)圖，V = 1,2,n。構(gòu)造G的最小生成樹Prim算法的基本 思想是：首先置S

23、= 1，然后，只要S是V的真子集，就進(jìn)行如下的貪心選擇：選取滿 足條件i S,j V - S,且cij 最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過程一直 進(jìn)行到S = V時(shí)為止。在這個(gè)過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。如下帶權(quán)圖：生成過程：1 -> 3 : 13 -> 6 : 46 -> 4: 23 -> 2 : 52 -> 5 : 3實(shí)現(xiàn)：三、Kruskal算法當(dāng)圖的邊數(shù)為 e時(shí)，Kruskal算法所需的時(shí)間是 O(eloge)。當(dāng)e = Q (nA2)時(shí)，Kruskal 算法比Prim算法差；但當(dāng) e =0(門人2)時(shí)，Kruskal算法比Prim算法

24、好得多。給定無(wú)向連同帶權(quán)圖G = (V,E),V= 1,2,.,n 。Kruskal算法構(gòu)造G的最小生成樹的基本思想是：(1)首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小大排序。(2 )從第一條邊開始，依邊權(quán)遞增的順序檢查每一條邊。并按照下述方法連接兩個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前兩個(gè)不同的連通分支T1和T2的端點(diǎn)是，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看k+1條邊。這個(gè)過程一個(gè)進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。此時(shí)，已構(gòu)成G的一棵最小生成樹。Kruskal算法的選邊過程：1 -> 3:14 -> 6:22 -> 5:33 -> 4:42 -> 3:5兩種算法代碼見教材2. 對(duì)數(shù)組A=15 , 29, 135,18, 32, 1 , 27, 25, 5，寫出用快速排序算法（按升序排序） 的第一