圖論及相關(guān)競(jìng)賽題講解ppt課件

1、圖論及相關(guān)競(jìng)賽題講解圖的數(shù)據(jù)構(gòu)造v圖G=(V, E)v點(diǎn)集Vv邊集E，邊(u, v)v權(quán)集W，邊(u,v)有權(quán)wv鄰接矩陣表示v鄰接表表示圖的數(shù)據(jù)構(gòu)造v鄰接矩陣v鄰接表1012345554683872084308670102055012345285348581641027521525圖的遍歷v可以用DFS或BFSv根據(jù)詳細(xì)情況選擇適宜的方法最短途徑vDijkstra算法：v設(shè)G=是個(gè)賦權(quán)圖。求一結(jié)點(diǎn)a到其他結(jié)點(diǎn)x的最短途徑長(zhǎng)度。步驟：v(1)把V分成兩個(gè)子集S和T。初始時(shí)，S=a，T=V-S。v(2)對(duì)T中每一元素t計(jì)算D(t)，根據(jù)D(t)值找出T中距a最短的一結(jié)點(diǎn)x，寫出a到x的最短途徑長(zhǎng)

2、度D(x)。v(3)置S為Sx，置T為T-x，假設(shè)T=，那么停頓，否那么再反復(fù)2v算法是基于“最短途徑的任一段子途徑都是最短途徑這一現(xiàn)實(shí)Dijkstra算法實(shí)例步驟步驟SxD(x)D(v1)D(v2)D(v3)D(v4)0a-2101a,v1v122592a,v1,v2v2525993a,v1,v2,v3v3925994全部全部v492599aV1V2V4V321073654Invitation Cards (zju2021 / pku1511)v知各站點(diǎn)間的乘車破費(fèi)。要從站點(diǎn)1乘車到各站點(diǎn)，然后從各站點(diǎn)乘車前往1。計(jì)算一下最小總破費(fèi)。(1站點(diǎn)個(gè)數(shù)1000000)輸入：輸入：22 21 2 1

3、32 1 334 61 2 102 1 601 3 203 4 102 4 54 1 50 輸出：輸出：46210最短途徑vFloyd算法：v 定義一個(gè)nn的方陣序列A0，A1，A2，An，其中Aki-1j-1表示從vi到vj允許k個(gè)頂點(diǎn)v0, v1,vk-1為中間頂點(diǎn)的最短途徑長(zhǎng)度(0kn)，并且A0等于圖的鄰接矩陣。A0ij表示從vi到vj不經(jīng)過任何中間頂點(diǎn)的最短途徑長(zhǎng)度。Anij就是從vi到vj的最短途徑長(zhǎng)度。vA0ij=arcsij0in-1, 0jn-1vAkij=minAk-1ij,Ak-1ik-1+Ak-1k-1j 1kn，參與第k個(gè)頂點(diǎn)vk-1為中間頂點(diǎn)。Floyd算法for(

4、k=0;kn;k+) for(i=0;in;i+) for( j=0;jdik+dkj) dij=dik+dkj; ( dij=Min(dij, dik+dkj) )Stockbroker Grapevine (zju1082)v股票經(jīng)紀(jì)人對(duì)謠言的過分反響是周知的。他受雇找一種在股市中分布謠言的方法，使之以最快的速度傳播出去。v他必需把謠言先傳給一個(gè)最適宜的人。輸入：輸入：32 2 4 3 52 1 2 3 62 1 2 2 253 4 4 2 8 5 31 5 84 1 6 4 10 2 7 5 202 2 5 1 50輸出：輸出：3 23 10Frogger (zju 1942)v湖中有一

5、些石頭顯露水面。青蛙Freddy蹲在其中一塊上面，他女朋友Fiona在另一塊上。Freddy想跳到Fiona那里。vFreddy可以在兩石頭間騰躍，有不同的途徑選擇；他希望找到一條路，路上騰躍的最大間隔最小。v輸入這些石頭的坐標(biāo)，輸出這個(gè)最小值。歐拉回路存在歐拉回路的條件：無向圖：一切頂點(diǎn)的度數(shù)都是偶數(shù)。有向圖：一切頂點(diǎn)的出度等于入度。混合圖：想方法把無向邊定向，使一切點(diǎn)出度等于入度。輸出歐拉回路的方法：DFS歐拉回路混合圖中的處置：無向邊隨意定向，生成一個(gè)有向圖，當(dāng)有結(jié)點(diǎn)的出入度之差為奇數(shù)，那么不存在歐拉回路。從一個(gè)出度大的點(diǎn)出發(fā)，尋覓一條途徑(途徑上的邊是原圖的無向邊) ，中止于出度小的點(diǎn)

6、。然后對(duì)這條途徑逆向。反復(fù)操作直到?jīng)]有出度大的點(diǎn)為止。Necklace (uva 10054)v一串項(xiàng)鏈的珠子有兩種顏色，串起來時(shí)要求相鄰顏色一樣。給了一些珠子，判別能否能串起來。輸入：輸入：251 22 33 44 55 652 12 23 43 12 4輸出：輸出：Case #1some beads may be lost Case #22 11 33 44 22 2Ouroboros Snake (uva 10040)v圓環(huán)上分布著2n個(gè)0、1，按順序延續(xù)取n個(gè)，就能把0 2n-1個(gè)整數(shù)都取到。(0n22)Euler Circuit (uva 10735)v在混合圖中判別能否存在歐拉回路

7、，存在那么輸出之。輸出：輸出：1 3 4 2 5 6 5 4 1No euler circuit exist輸入：輸入：26 81 3 U1 4 U2 4 U2 5 D3 4 D4 5 U5 6 D5 6 U4 41 2 D1 4 D2 3 U3 4 U哈密爾頓回路v直接用DFS搜索尋覓。最小生成樹vPrim算法v設(shè)G=(V,E)是無向圖，求它的最小生成樹T=(V,E)的Prim算法為：v從V中任取一結(jié)點(diǎn)放入V；v在一切的端點(diǎn)分別在(V-V)和V中的邊中，選一條權(quán)最小的參與E；v將邊E在(V-V)中的頂點(diǎn)從V中取出放入V；v反復(fù)步驟，直到V與V相等為止。最小生成樹v構(gòu)造以下圖的最小生成樹V2V

8、2V0V0V3V3V5V5V4V4V1 V2 2V V0 0V V3 3V V5 5V V4 4V V1 1V2V2V0V0V V3 3V V5 5V V4 4V V1 11V V3 3V V4 4V V1 141V0V0V2V2V5V5V V4 4V V1 1214V0V0V2V2V5V5V3V3V V4 41425V2V2V0V0V5V5V1V1V3V335124V2V2V1V1V0V0V5V5V3V3V4V4U=v0U=v0,v2U=v0,v2,v5U=v0,v2,v5,v3U=v0,v2,v5,v3,v1U=v0,v2,v5,v3,v1,v4Prim 算法數(shù)據(jù)

9、構(gòu)造1243566165556342 圖圖G1243566165556342 圖圖G1243566165556342 圖圖GUU012345 數(shù)組：數(shù)組：lowcost 6 數(shù)組：數(shù)組：lowcost 6 留意：留意：lowcost 0 = 0lowcost 表示最小間隔表示最小間隔0615012345050564最小生成樹vKruscal算法v把邊按權(quán)值遞減排序，按順序每次添加一條邊，假設(shè)產(chǎn)生回路那么舍棄。當(dāng)把一切點(diǎn)都連通起來，那么得到最小生成樹。Kruscal 算法的實(shí)例 實(shí)例的執(zhí)行過程實(shí)例的執(zhí)行過程1243566165556342 圖圖G1、初始連通分量：、初始連通分量：1,2,3,4,

10、5,62、反復(fù)執(zhí)行、反復(fù)執(zhí)行“添加、添加、“放棄動(dòng)作。條件：邊數(shù)不等于放棄動(dòng)作。條件：邊數(shù)不等于 n-1時(shí)時(shí) 邊邊 動(dòng)作動(dòng)作連通分量連通分量 (1,3) 添加添加1,3,4,5,6,2 (4,6) 添加添加1,3,4, 6,2,5 (2,5) 添加添加1,3,4, 6,2,5 (3,6) 添加添加1,3,4, 6,2,5 (1,4) 放棄放棄因構(gòu)成回路因構(gòu)成回路 (3,4) 放棄放棄因構(gòu)成回路因構(gòu)成回路 (2,3) 添加添加1,3,4,5,6,2算法實(shí)現(xiàn)要點(diǎn)算法實(shí)現(xiàn)要點(diǎn): 用并查集的相關(guān)操作：實(shí)現(xiàn)集合的并；判別用并查集的相關(guān)操作：實(shí)現(xiàn)集合的并；判別新邊的兩端點(diǎn)能否處于同一集合，來確定能否構(gòu)成回路。新邊的兩端點(diǎn)能否處于同一集合，來確定能否構(gòu)成回路。最小代價(jià)生成樹最小代價(jià)生成樹1243561534255Kruscal 算法數(shù)據(jù)構(gòu)造v優(yōu)先隊(duì)列(把一切邊按長(zhǎng)度遞增的順序保管在一個(gè)表里)v并查集并查集 (Union-Find Sets)v先把每一個(gè)對(duì)象看作是一個(gè)單元素集合，然后按一定順序?qū)⑾嚓P(guān)聯(lián)的元素所在的集合合并?？梢酝瓿蛇@種功能的集合就是并查集。v對(duì)于并查集來說，每個(gè)集合用一棵樹表示。v它支持以下操作：vUnite (Root1, Root2) /并操作vFind (x) /搜索操作搜