ds上機考試題目概述第f365

1、第7章 圖27.6 圖的遍歷7.7 最短路徑7.9 最小支撐樹7.10圖匹配12011/11/97.6圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點V0出發(fā)，此頂點；然后依次從V0的未被的鄰接點出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被到；若此時圖中尚有頂點的頂點作起點，重復未被，則另選圖中一個未被上述過程，直至圖中所有頂點都被時候會出現(xiàn)這種情況？）為止（問題：什么V1例類似于：樹的前序遍歷！V2V3V4V5V6V7V8深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1例V2V3V4V5V6V7V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1例V3V2

2、V5V6V4V8V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V732011/11/9V1例V2V3V4V5V6V7V8深度遍歷：V1 V2 V4 V8 V3 V6 V7 V542011/11/9深度優(yōu)先遍歷算法遞歸算法開始開始v,置標志標志數組初始化求v鄰接點Vi=1N有鄰接點uYNVi過DFSY Yu過NuvVi=Vi+1求下NVi=VexnumsY結束DFS結束一鄰接點V1例V2V3V4V5V6V7深度遍歷：V1V3 V7 V6 V2 V5 V8 V4V8vexdataarcadjvex next2462233412343578876511567812345678V1例V2V3

3、V4V5V6V7深度遍歷：V1V3 V7 V6 V2 V4 V8 V5V8vexdataarcadjvex next34788721234567862123456787.6 圖的遍歷廣度優(yōu)先搜索(BFS)方法：從圖的某一頂點V0出發(fā)，此頂點后，依次訪問V0的各個未曾過的鄰接頂點；然后分別從這些鄰接頂點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被的頂，點的鄰接點都被到；若此時圖中尚有頂點未被則另選圖中一個未被直至圖中所有頂點都被的頂點作起點，重復上述過程，為止。V1例類似于：樹的層次遍歷！V2V3V4V5V6V7V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1例V2V3V4V5V6V7

4、V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1例V3V2V5V6V4V8V7廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V892011/11/9V1例V2V3V4V5V6V7V8廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V5102011/11/9廣度優(yōu)先遍歷算法開始標志數組初始化Vi=1NVi過BFSYVi=Vi+1NV =VexnumsiY結束112011/11/9開始問題：可否在出隊時（P150）和入隊前區(qū)別？BFSv置標志頂點？初始化隊列有何v入隊Y隊列空嗎N隊頭w出隊au,置標志結束求w鄰接點uu入隊Nw下一鄰接點uu存在嗎YYu過Na廣度優(yōu)先遍歷算

5、法vexdataarcadjvex next24555431113例52fff 144301234501r2345012r345r遍歷序列：1遍歷序列：1 4遍歷序列：1 4 32011/11/912345vexdataarcadjvex next24555431113例52fff4322250123r45rr遍歷序列：遍歷序列：遍歷序列：1 4 3 2 52011/11/912345vexdataarcadjvex next24555431113例23452fff255 01234r5rr遍歷序列：遍歷序列：遍歷序列：152011/11/9123457.7 最短路徑問題提出用帶權的有向圖表示

6、一個交通頂點表示城市邊表示城市間的交通聯(lián)系網，圖中：權表示此線路的長度或沿此線路費用等問題：從某頂點出發(fā)，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑最短路徑。單源最短路徑所花的時間或082536432131973061752最短路徑長Dijkstra算法按路徑長度遞增次序產生最短路徑算法：把V分成兩組：（1）S：已求出最短路徑的頂點的集合（2）V-S=T：尚未確定最短路徑的頂點集合將T中頂點按最短路徑遞增的次序加入到S中，保證：從源點V0到S中各頂點的最短路徑長度都不大于從V0到T中任何頂點的最短路徑長度每個頂點對應一個距離值S中頂點：從V0到此

7、頂點的最短路徑長度T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和。求最短路徑步驟：初始時令 S=V0,T=其余頂點，T中頂點對應的距離值若存在，距離值為弧上的權值若不存在，距離值為從T中選取一個其距離值為最小的頂點W，加入S對T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的距離值比不加W的路徑要短，則修改此距離值重復上述步驟，直到S中包含所有頂點，即S=V為止算法實現(xiàn)圖用帶權鄰接矩陣a 數組dist 存放當前找到的從源點V0到每個終點的最短路徑長度

8、，其初態(tài)為圖中直接路徑權值數組pre 表示從V0到各終點的最短路徑上，此頂點的前一頂點的序號；若從V0到某終點無路徑，則用0作為其前一頂點的序號192011/11/9算法描述步驟1：初始化distv=asv,0=v1， distku=mindistk-1v+e(v,u) (v,u) E。Bellman-Ford最短路算法就是依次遞歸式計算最短路。所有頂點對之間的最短路徑方法一：每次以一個頂點為源點，重復執(zhí)行Dijkstra算法n次 T(n)=O(n)方法二： Floyd算法算法：逐個頂點試探法求最短路徑步驟初始時設置一個n階方陣，令其對角線元素為0，若存在弧，則對應元素為權值；否則為逐步試著在

9、原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值所有頂點試探完畢，算法結束242011/11/9Floyd算法實現(xiàn)設V= 0,1,，n -1。設置一個nn矩陣c，初始時ci,j= ai,j。在矩陣c上做n次迭代。經第k次迭代之后，ci,j的值是從頂點i到頂點j，且中間不經過大于k的頂點的最短路徑長度。在c上做第k次迭代時，用下面的公式來計算：ci,j = min ci,j, ci,k+ck,j 6411C例AB300000000020401120初始： 63path=路徑0000010000634071120加入A：路徑path=063407620000001200加

10、入B：路徑path=053407620030001200加入C：路徑：path=ABABCBCABCCACABABABC： BABCCACABABAC： BABCCACABABAC： BABCCA算法實現(xiàn)圖用鄰接矩陣二維數組c 存放最短路徑長度pathij是從Vi到Vj的最短路徑上Vj前一頂點序號算法描述這樣看來， Floyd算法似乎沒帶來更多的好處？！T(n)=O(n3)算法分析實際上，從實現(xiàn)代碼來看：Floyd算法的代碼比用Dijkstra算法要簡明得多！272011/11/97.9 支撐樹（生成樹）定義：所有頂點均由邊連接在一起，但不存在回路的圖叫說明：一個圖可以有許多棵不同的生成樹所有

11、生成樹具有以下共同特點：生成樹的頂點個數與圖的頂點個數相同生成樹是圖的極小連通子圖一個有n個頂點的連通圖的生成樹有n-1條邊生成樹中任意兩個頂點間的路徑是唯一的G在生成樹中再加一條邊必然形成回路含n個頂點n-1條邊的圖不一定是生成樹KIH282011/11/9 最小支撐樹（最小生成樹）問題提出要在n個城市間建立通信聯(lián)絡網，頂點表示城市權城市間建立通信線路所需花費代價75924101218希望找到一棵生成樹，它的每條邊上的權值之和（即建立該通信網所需花費的總代價）最小最小代價生成樹問題分析n個城市間，最多可設置n(n-1)/2條線路 n個城市間建立通信網，只需n-1條線路問題轉化為：如何在可能的

12、線路中選擇n-1條，能把所有城市（頂點）均連起來，且總耗費（各邊權值之和）最小 最小生成樹性質用貪心算法設計策略可以設計出構造最小生成樹的有效算法。本節(jié)介紹的構造最小生成樹的Prim算法和 Kruskal算法都可以看作是應用貪心算法設計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們用了下面的最小生成樹性質：設G=(V,E)是連通帶權圖，U是V的真子集。如果 (u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質有時也稱為MST性質。302011/11/9 MST性質證明假設G的任何一棵最小生成樹都

13、不含邊(u,v)。將邊(u,v)添加到G的一棵最小生成樹T上，將產生含有邊(u,v)的圈，并且在這個圈上有一條不同于 (u,v)的邊(u,v)，使得uU,vV-U，如下圖所示。圖示 含邊(u,v)的圈將邊(u,v)刪去，得到G的另一棵生成樹T。由于cuvcuv，所以T的耗費T的耗費。于是T是一棵含有邊(u,v)的最小生成樹，這與假設。構造最小生成樹方法方法一：Prim算法：設G=(V,E)是連通網，T是N上最小生成樹中算法邊的集合初始令U=u0,(u0V), T=在所有uU,vV-U的邊(u,v)E中，找一條代價最小的邊(u0,v0)將(u0,v0)并入集合T，同時v0并入U重復上述操作直至U

14、=V為止，則T=(V, T)為N的最小生成樹算法實現(xiàn)：圖用鄰接矩陣表示算法描述算法評價：T(n)=O(n)322011/11/9例52466532構造最小生成樹方法方法二：Kruskal算法：設G=(V,E)，令最小生成樹算法初始狀態(tài)為只有n個頂點而無邊的非連通圖T=(V,)，每個頂點自成通分量在E中選取代價最小的邊，若該附的頂點落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價最小的邊依此類推，直至T中所有頂點都在同一連通分量上為止例52466方法二：Kruskal算法算法描述：算法分析：設輸入的連通賦權圖有e條邊，則將這些其權值組成優(yōu)先隊列需要O(e)時間；whi

15、le循環(huán)中，DeleteMin運算需要O(loge)時間，因此關于優(yōu)先隊列所作運算的時間為O(eloge)。實現(xiàn)UnionFind所需的時間為O(eloge)。 Kruskal算法所需的計算時間是O(eloge)。Prim算法與Kruskal算法的比較從算法的時間復雜性看:(n2)時，Kruskal算法比Prim算法差，當e=但當e=O(n2)時，Kruskal算法卻比Prim算法好得多。7.10 圖匹配算法設G=(V,E)是一個無向圖。如果頂點集合V可分割為2個互不相交的子集，并且圖中每條邊(i,j)所關聯(lián)的2頂點i和j分屬于這2個不同的頂點集，則稱圖G為一個二分圖。在學校的教務管理中，排課

16、表是一項例行工作。一般情況下每位教師可勝任多門課程的教學，而每個學期 只講授一門所勝任的課程。反之每學期的一門課程只 需一位教師講授。這就需要對課程和教師作合理安排?？梢杂靡粋€二分圖來表示教師與課程的這種關系。教 師和課程都是圖的頂點，邊(t,c)表示教師t勝任課程c。圖匹配問題可描述如下：設G =(V,E)是一個圖。如果M E，且M中任何2條邊都不與同一個頂點相關聯(lián)，則稱 M是G的一個匹配。G的邊數最多的匹配稱為G的最大匹配。如果圖的一個匹配使得圖中每個頂點都是該匹配中某條邊的端點，那么就稱這個匹配為圖的一個完全匹配。一個圖的完全匹配一定是這個圖的一個最大匹配。為了求一個圖的最大匹配，可以系統(tǒng)地列舉出該圖的所有匹配，然后從中選出邊數最多者。這種方法所需要的時間是圖中邊數的一個指數函數。因此，需要一種更有效的算法。設M是圖G的一個匹配，將M中每邊所關聯(lián)的頂點稱為已匹配頂點，其余頂點稱為未匹配頂點。若p是圖G中一條連通2個未匹配頂點的路徑，并且在路徑p上屬于M的邊和不屬于M的邊交替出現(xiàn)，則稱p為一條關于M的增廣路徑。由此定義可知增廣路徑具有以下性質：一條關于M的增廣路徑的長度必為