干圖論專題精品課件

1、干圖論專題第1頁，共41頁，2022年，5月20日，6點48分，星期三內(nèi)容介紹拓撲排序歐拉道路和回路最小生成樹問題最短路問題第2頁，共41頁，2022年，5月20日，6點48分，星期三基本概念圖G=(V, E)點集V邊集E，邊(u, v)權集W，邊(u,v)有權w圖形表示鄰接矩陣表示鄰接表表示前向星表示第3頁，共41頁，2022年，5月20日，6點48分，星期三拓撲排序網(wǎng)線從機房連接到辦公室在機房，所有網(wǎng)線從左到右編號為1,2,3,N 給出每兩條線是否交叉的信息，請計算辦公室內(nèi)從左到右各條線的編號 第4頁，共41頁，2022年，5月20日，6點48分，星期三拓撲排序核心問題：給一些序關系，排出

2、全序！一個一個排先排最大然后第二大具體實現(xiàn)？每次取0出度點枚舉所有點嗎？0出度只可能是1出度變來的！O(n+m)第5頁，共41頁，2022年，5月20日，6點48分，星期三歐拉道路和回路經(jīng)過每條邊一次且僅一次先看回路必要條件：所有點度為偶數(shù)充分條件：還是“所有點度為偶數(shù)”證明！把歐拉回路構造出來“圈套圈”可能套不出來嗎？想一想第6頁，共41頁，2022年，5月20日，6點48分，星期三歐拉道路和回路有向的情形入度 = 出度如何套圈？道路有兩個奇度點正好是起點和終點哪個是起點，哪個是終點？有向+無向怎么辦？網(wǎng)絡流！不要求掌握第7頁，共41頁，2022年，5月20日，6點48分，星期三一個例子幼兒

3、園里有很多房屋房屋與房屋之間連以走廊走廊與房屋之間有一扇門幼兒園長想把門漆成綠色或者黃色，使得任意一條走廊兩頭門的顏色不同任意一間房屋上的門，綠色門的數(shù)量與黃色門的數(shù)量相差不超過1。 如何實現(xiàn)？每個房屋的門都是偶數(shù)個把奇數(shù)改造成偶數(shù)！第8頁，共41頁，2022年，5月20日，6點48分，星期三另一個例子考古學家發(fā)現(xiàn)了一塊布，布上做有針線活，叫做“十字繡”交替地在布的兩面穿線布是一個nm的網(wǎng)格線只能在網(wǎng)格的頂點處才能從布的一面穿到另一面。每一段線都覆蓋一個單位網(wǎng)格的兩條對角線之一而在繡的過程中，一針中連續(xù)的兩段線必須分處布的兩面給出布兩面的圖案（實線代表有線，虛線代表背面有線）最少需要幾針才能繡

4、出來？一針是指針不離開布的一次繡花過程。例如圖(b)的圖案最少需要4針。 第9頁，共41頁，2022年，5月20日，6點48分，星期三分析抽象成圖正面的線：正邊背面的線：負邊有邊相連：連通塊每個連通塊分別求對于某個頂點I|正邊數(shù)-負邊數(shù)|=K0時以該頂點為開始或結束的針數(shù)=K可以恰好為K針所有K值加起來，除以2（每一針有兩個端點）第10頁，共41頁，2022年，5月20日，6點48分，星期三最小生成樹問題要求連接所有島嶼電纜總長度盡量小第11頁，共41頁，2022年，5月20日，6點48分，星期三Prim算法任意時刻的中間結果都是一棵樹從一個點開始每次都花最小的代價，用一條加進一個新點問題：這

5、樣做是對的嗎？如何快速找到這個“最小代價”？第12頁，共41頁，2022年，5月20日，6點48分，星期三Prim算法的正確性換一種說法如果存在一個MST，包含當前所有邊則它一定包含最小代價邊(u, v)反證法！假設存在這樣的MST，包含當前所有邊但不包含(u, v)當前結點集為S，剩下的結點集為T由于在MST中S-T連通一定有跨越S-T的某邊(u,v)它不是最小代價邊(u,v)刪除(u,v)，加入(u,v)，S和T分別連通，且S-T通過(u,v)連通得到了一個更小的MST！第13頁，共41頁，2022年，5月20日，6點48分，星期三快速找到最小代價需要借助數(shù)據(jù)結構！我們的算法要求快速取/刪

6、除最小值（邊權）允許插入邊（加入新點時插入它的關接邊）抽象數(shù)據(jù)類型：優(yōu)先隊列！經(jīng)典實現(xiàn)：堆！堆是一棵完全二叉樹每個結點有一個權值根的權值最小根的左右子樹都是堆第14頁，共41頁，2022年，5月20日，6點48分，星期三堆的操作插入插在哪里可以保持完全二叉樹的形態(tài)呢？插最后！怎樣維持堆的根最小性質呢？向上調整（和父親交換）刪除怎樣保持完全二叉樹形態(tài)呢？和最后一個元素交換，再直接刪除怎樣維持堆的根最小性質呢？向下調整（和兩個兒子比較，和較小的交換）時間復雜度：均為O(logn)還有一個操作：取最小值，怎么實現(xiàn)？第15頁，共41頁，2022年，5月20日，6點48分，星期三堆的實現(xiàn)完全二叉樹可以用

7、數(shù)組heap1.maxn實現(xiàn)結點i的父親：i div 2左兒子：2*i右兒子：2*i+1存在條件：i = nodecount不用指針！利用了數(shù)組的“隨機存取”特性！插入刪除過程 用循環(huán)，不要用遞歸第16頁，共41頁，2022年，5月20日，6點48分，星期三Prim算法框架初始化，樹僅含一個任意一點v0把v0的鄰邊插入堆for i:=1 to n-1 dobegin 從堆中取出最小值，設邊為(u,v)，v為新點 (u,v)加入生成樹中 v和它所有不在樹中的鄰居組成的邊插入堆end;每次取最小值為O(logm)總時間復雜度為O(nlogm)第17頁，共41頁，2022年，5月20日，6點48分，

8、星期三Kruskal算法任意時刻的中間結果是一個森林從n個點的集合開始每次選不產(chǎn)生圈的前提下權最小的邊加入問題：這樣做是對的嗎？如何快速的判斷是否產(chǎn)生圈第18頁，共41頁，2022年，5月20日，6點48分，星期三Kruskal算法的正確性把一個二元組(E, I)叫做一個子集系統(tǒng)，如果滿足：1E是一個非空集合2I是E的一個子集族，它在包含運算下封閉，即I的每個元素a都是E的一個子集，并對于a的任何子集a，a一定也是I的元素。3給E中每個元素e賦予一個正權w(e)?？紤]至少有一條邊的帶權無向連通圖G它的邊集為E它的所有生成森林的集合為I則(E,I)是一個子集系統(tǒng)，稱為生成森林子集系統(tǒng)E非空，所以

9、滿足條件1生成森林是E的一個邊集，而且其生成子圖仍是生成森林，滿足2G是帶權的，所以滿足3。 第19頁，共41頁，2022年，5月20日，6點48分，星期三子集優(yōu)化問題極大獨立集把I中的元素都稱為獨立集對于I中的元素a，如果不存在I中的另一個元素a使得a是a的真子集，則稱a是極大獨立集。該極大獨立集的基數(shù)為它包含的元素個數(shù)在剛才介紹的子集系統(tǒng)中，G的所有生成樹就是所有的極大獨立集。所有極大獨立集具有相同的基數(shù)|V|-1。其中|V|為G的頂點數(shù)。子集優(yōu)化問題在子集系統(tǒng)(E, I)中選取一個元素SI，使得w(S)最大（定義w(S)為S中所有元素的權和） 第20頁，共41頁，2022年，5月20日，

10、6點48分，星期三子集優(yōu)化問題的貪心算法貪心算法先把E中元素按照權值從大到小排序為e1,e2,令集合S=空集然后每次嘗試著把e1,e2,，添加到S里面如果添加之后S仍是獨立集，則添加成功如果S不是獨立集，則由定義知以后無論怎樣繼續(xù)添加元素，得到的集合都不可能重新成為獨立集，因此撤消此添加操作。 Kruskal算法是生成森林子集系統(tǒng)的貪心算法！貪心算法在什么子集系統(tǒng)下是的對的呢？定理貪心算法正確，當且僅當這個系統(tǒng)的極大獨立集具有相同的基數(shù)滿足條件的子集系統(tǒng)稱為“矩陣胚(matroid)”第21頁，共41頁，2022年，5月20日，6點48分，星期三快速判斷是否產(chǎn)生圈需要借助數(shù)據(jù)結構！我們的算法要

11、求判斷兩個點是否在同一棵樹中產(chǎn)生圈當且僅當此邊連接同一樹中的點！快速把兩棵樹合并加邊意味著兩棵樹合為一棵抽象數(shù)據(jù)類型：并查集！經(jīng)典實現(xiàn)：森林并查集的森林實現(xiàn)森林中的每棵樹表示不同的集合樹的形態(tài)并不重要，有意義的只是“哪些元素在樹中”第22頁，共41頁，2022年，5月20日，6點48分，星期三并查集的操作查找用樹根作為集合的標識不斷的找父親，最終將找到樹根要找多少次父親？和樹的高度有關！怎樣減少樹的高度？找到樹根后沿途把路徑上的結點的父親設為根專門名稱：路徑壓縮兩元素所在的樹根相同，則二者屬于同一集合合并其中一棵樹成為另一棵樹樹根的子樹誰成為誰的子樹？注意樹的高度！啟發(fā)式合并時間復雜度：幾乎都

12、為常數(shù)！第23頁，共41頁，2022年，5月20日，6點48分，星期三并查集的實現(xiàn)回憶剛才用到了什么信息？查找：“不斷的找父親”“沿途設置結點的父親為樹根”合并：“把一棵樹的父親設置為另一棵樹的樹根”只有“父親”信息！父親表示法！father : array1.maxn of integer;根結點root滿足fatherroot := root查找：while fatherp p do p := fatherp; ?合并：if height(p1) height(p2) then fatherp1 := p2第24頁，共41頁，2022年，5月20日，6點48分，星期三Kruskal算法框架

13、把所有邊按照權值從小到大排序為e1,e2,初始化n個集合，Si=isize := 0;for i:=1 to m do if ei的兩個端點u, v不在同一個集合 then begin 合并Su和Sv inc(size); if size = n 1 then break; end;最壞情況循環(huán)執(zhí)行m次，判斷約O(1)如果輸入已經(jīng)排序好，則總時間復雜度為O(m)，否則為O(mlogm)第25頁，共41頁，2022年，5月20日，6點48分，星期三最短路問題問題描述：給加權圖GSSSP：求給定起點s到其他所有點的最短路APSP：求每兩對點的最短路算法標號設定類：dijkstra標號修正類：bel

14、lman-ford動態(tài)規(guī)劃類：floyd-warshall變形與應用舉例第26頁，共41頁，2022年，5月20日，6點48分，星期三SSSP：權非負的情形求1到所有點的距離d1 = 0d2 = 3, d4 = 4d2 = 3. 為什么？每次固定d的最小值標號設定！怎樣取最小值？堆！名稱：dijkstra和Prim算法很類似Prim: 邊最小值dijkstra: d最小值中間結果：最短路樹！時間復雜度O(m+n)logm)第27頁，共41頁，2022年，5月20日，6點48分，星期三一個例子給出一個帶權無向圖G邊權為11 000的整數(shù)對于v0到v1的任意一條簡單路p定義s(p)為p上所有邊權的

15、最大公約數(shù)考慮v0到v1的所有路p1,p2,求所有s(p1),s(p2),的最小公倍數(shù)模型？最短路？路徑長度定義不再是權和，而是dijkstra算法還能用嗎？第28頁，共41頁，2022年，5月20日，6點48分，星期三SSSP：權任意的情形最短路有可能不存在！ 什么時候不存在？ 有負圈！標號設定標號修正仍然有標號di = k但是標號di無法固定，只能不斷更新新算法如有最短路，則每個頂點最多經(jīng)過一次即：這條路不超過n-1條邊 迭代！依次考慮1,2,3n-1條邊的情形第29頁，共41頁，2022年，5月20日，6點48分，星期三SSSP：bellman-ford算法依次考慮邊長度不超過1,2n-

16、1的路考慮長度不超過1,2,3k-1的路后，標號為d長度為k的路可以由不超過1,2,k-1的路增加一條邊得到：for k:=1 to n-1 do for 每條邊(u,v) do if (dudu+w(u,v) then dv:=du+w(u,v) 核心：標號修正過程（松弛操作）時間復雜度：O(nm)改進的終止條件：d都不改變加速：用dijkstra得到初始d第30頁，共41頁，2022年，5月20日，6點48分，星期三一個例子24小時營業(yè)的超市需要一批出納員來滿足它的需求每天的不同時段需要不同數(shù)目的出納員例如：午夜時只需一小批，而下午則需要很多）經(jīng)理已經(jīng)提供你一天里每一小時需要出納員的最少數(shù)

17、量R(0), R(1), , R(23)。R(0)表示從午夜到午夜1:00需要出納員的最少數(shù)目，R(1)表示上午1:00到2:00之間需要的每一天，這些數(shù)據(jù)都是相同的。有N人申請這項工作每個申請者i在每天24小時中，從一特定的時刻開始連續(xù)工作恰好8小時定義ti（0ti23）為上面提到的開始時刻也就是說，如果第i個申請者被錄用，他將從ti刻開始連續(xù)工作8小時。計算為滿足上述限制需要雇傭的最少出納員數(shù)目在每一時刻可以有比對應的R(i)更多的出納員在工作。 第31頁，共41頁，2022年，5月20日，6點48分，星期三分析前i(0=i=23)小時的雇傭總數(shù)：si規(guī)定s-1 = 0第i(0=i=23)

18、小時需要的出納員：ri第i(0=i=23)小時申請的人數(shù)：ti則有不等式0 = si si-1 j時 si sj = riI = ri sumsum已知道時構圖G(-1,0,1,23)Sa sb = c：有向邊(b, a, c)-1為起點的單源最長路最長路存在且s23 = sum，有解枚舉sum！二分？第32頁，共41頁，2022年，5月20日，6點48分，星期三APSP: 基本分析設di，j，k是在只允許經(jīng)過結點1k的情況下i到j的最短路長度則它有兩種情況（想一想，為什么）：如果最短路經(jīng)過點k，那么di，j，k應該等于di，k，k-1+dk，j，k-1；如果最短路不經(jīng)過點k，那么di，j，k

19、應該等于di，j，k-1。綜合起來di，j，k=mindi，k，k-1+dk，j，k-1，di，j，k-1邊界條件是di，j，0=w(i，j)（不存在的邊權為） 第33頁，共41頁，2022年，5月20日，6點48分，星期三floyd-warshall算法基本的動態(tài)規(guī)劃把k放外層循環(huán)，可以節(jié)省內(nèi)存對于每個k，計算每兩點的目前最短路for k:=1 to n dofor i:=1 to n do for j:=1 to n do if (di,k)and(dk,j) and(di,k+dk,jdi,j) then di,j:=di,k+dk,j一定要背下來！時間復雜度：O(n3)用途：預處理！第

20、34頁，共41頁，2022年，5月20日，6點48分，星期三一個例子一場可怕的戰(zhàn)爭后，瘦陀陀和他的好朋友胖陀陀將要凱旋。瘦陀陀處在城市A胖陀陀處在另外一個未知的城市他們打算選一個城市X（這個由瘦陀陀來決定）胖陀陀會趕在瘦陀陀之前到達城市X然后等待瘦陀陀也趕到城市X與他匯合，并舉辦一次慶祝宴會（由瘦陀陀請客）接著一起回到他們的家鄉(xiāng)城市B由于胖陀陀嘴饞，他要求舉辦宴會的城市必須是瘦陀陀回家的路線中舉辦宴會最貴的一個城市。 第35頁，共41頁，2022年，5月20日，6點48分，星期三一個例子（續(xù)）瘦陀陀正專注地看回家的地圖地圖上標有n（n200）個城市和某些城市間直達的道路以及每條道路的過路費瘦陀

21、陀還知道在每一座城市舉辦宴會的花費。給出地圖和A、B的位置請你告訴瘦陀陀回家的最小費用你的程序會接收到多次詢問即對于每對城市(c1,c2)，你的程序應該立刻給出瘦陀陀從c1到c2的最小花費。 第36頁，共41頁，2022年，5月20日，6點48分，星期三分析胖陀陀規(guī)定必須在最貴的城市舉辦宴會因此不能簡單地選擇一條最短路走若路上有一個花費特別貴的城市對于每個點X，如果在那里辦宴會如何求最短路？多個詢問怎么處理？floyd計算每兩點的距離？SSSP就可以勝任嗎？AB = AX + XB第37頁，共41頁，2022年，5月20日，6點48分，星期三討論題目（一）沒有水或食物，你將無法前行為了穿越沙漠，應該購買多少食物呢？在出發(fā)地，你可以采購食物和獲得無限多的免費水但由于背包容量有限，在任意時候擁有的水和食物總量不得超過一個