干圖論專題精品課件

1、干圖論專題第1頁(yè)，共41頁(yè)，2022年，5月20日，6點(diǎn)48分，星期三內(nèi)容介紹拓?fù)渑判驓W拉道路和回路最小生成樹(shù)問(wèn)題最短路問(wèn)題第2頁(yè)，共41頁(yè)，2022年，5月20日，6點(diǎn)48分，星期三基本概念圖G=(V, E)點(diǎn)集V邊集E，邊(u, v)權(quán)集W，邊(u,v)有權(quán)w圖形表示鄰接矩陣表示鄰接表表示前向星表示第3頁(yè)，共41頁(yè)，2022年，5月20日，6點(diǎn)48分，星期三拓?fù)渑判蚓W(wǎng)線從機(jī)房連接到辦公室在機(jī)房，所有網(wǎng)線從左到右編號(hào)為1,2,3,N 給出每?jī)蓷l線是否交叉的信息，請(qǐng)計(jì)算辦公室內(nèi)從左到右各條線的編號(hào) 第4頁(yè)，共41頁(yè)，2022年，5月20日，6點(diǎn)48分，星期三拓?fù)渑判蚝诵膯?wèn)題：給一些序關(guān)系，排出

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、1的路考慮長(zhǎng)度不超過(guò)1,2,3k-1的路后，標(biāo)號(hào)為d長(zhǎng)度為k的路可以由不超過(guò)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) 核心：標(biāo)號(hào)修正過(guò)程（松弛操作）時(shí)間復(fù)雜度：O(nm)改進(jìn)的終止條件：d都不改變加速：用dijkstra得到初始d第30頁(yè)，共41頁(yè)，2022年，5月20日，6點(diǎn)48分，星期三一個(gè)例子24小時(shí)營(yíng)業(yè)的超市需要一批出納員來(lái)滿足它的需求每天的不同時(shí)段需要不同數(shù)目的出納員例如：午夜時(shí)只需一小批，而下午則需要很多）經(jīng)理已經(jīng)提供你一天里每一小時(shí)需要出納員的最少數(shù)

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

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

19、應(yīng)該等于di，j，k-1。綜合起來(lái)di，j，k=mindi，k，k-1+dk，j，k-1，di，j，k-1邊界條件是di，j，0=w(i，j)（不存在的邊權(quán)為） 第33頁(yè)，共41頁(yè)，2022年，5月20日，6點(diǎn)48分，星期三floyd-warshall算法基本的動(dòng)態(tài)規(guī)劃把k放外層循環(huán)，可以節(jié)省內(nèi)存對(duì)于每個(gè)k，計(jì)算每?jī)牲c(diǎn)的目前最短路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一定要背下來(lái)！時(shí)間復(fù)雜度：O(n3)用途：預(yù)處理！第

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

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