圖論及相關(guān)競賽題講解.ppt

圖論及相關(guān)競賽題講解,圖的數(shù)據(jù)結(jié)構(gòu),圖G=(V, E) 點(diǎn)集V 邊集E，邊(u, v) 權(quán)集W，邊(u,v)有權(quán)w 鄰接矩陣表示 鄰接表表示,圖的數(shù)據(jù)結(jié)構(gòu),鄰接矩陣 鄰接表,圖的遍歷,可以用DFS或BFS 根據(jù)具體情況選擇合適的方法,最短路徑,Dijkstra算法： 設(shè)G=是個賦權(quán)圖。求一結(jié)點(diǎn)a到其他結(jié)點(diǎn)x的最短路徑長度。步驟： (1)把V分成兩個子集S和T。初始時，S=a，T=V-S。 (2)對T中每一元素t計(jì)算D(t)，根據(jù)D(t)值找出T中距a最短的一結(jié)點(diǎn)x，寫出a到x的最短路徑長度D(x)。 (3)置S為Sx，置T為T-x，若T=，則停止，否則再重復(fù)2 算法是基于“最短路徑的任一段子路徑都是最短路徑”這一事實(shí),Dijkstra算法實(shí)例,Invitation Cards (zju2008 / pku1511),已知各站點(diǎn)間的乘車花費(fèi)。要從站點(diǎn)1乘車到各站點(diǎn)，然后從各站點(diǎn)乘車返回1。計(jì)算一下最小總花費(fèi)。(1站點(diǎn)個數(shù)1000000),輸入： 2 2 2 1 2 13 2 1 33 4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50,輸出： 46 210,最短路徑,Floyd算法： 定義一個nn的方陣序列A0，A1，A2，An，其中Aki-1j-1表示從vi到vj允許k個頂點(diǎn)v0, v1,vk-1為中間頂點(diǎn)的最短路徑長度(0kn)，并且A0等于圖的鄰接矩陣。A0ij表示從vi到vj不經(jīng)過任何中間頂點(diǎn)的最短路徑長度。Anij就是從vi到vj的最短路徑長度。 A0ij=arcsij 0in-1, 0jn-1 Akij=minAk-1ij,Ak-1ik-1+Ak-1k-1j 1kn，加入第k個頂點(diǎn)vk-1為中間頂點(diǎn)。,Floyd算法,for(k=0;kdik+dkj) dij=dik+dkj; ( dij=Min(dij, dik+dkj) ),Stockbroker Grapevine (zju1082),股票經(jīng)紀(jì)人對謠言的過分反應(yīng)是周知的。你受雇找一種在股市中散布謠言的方法，使之以最快的速度傳播出去。 你必須把謠言先傳給一個最合適的人。,輸入： 3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 0 2 2 5 1 5 0,輸出： 3 2 3 10,Frogger (zju 1942),湖中有一些石頭露出水面。青蛙Freddy蹲在其中一塊上面，他女朋友Fiona在另一塊上。Freddy想跳到Fiona那里。 Freddy可以在兩石頭間跳躍，有不同的路徑選擇；他希望找到一條路，路上跳躍的最大距離最小。 輸入這些石頭的坐標(biāo)，輸出這個最小值。,歐拉回路,存在歐拉回路的條件： 無向圖：所有頂點(diǎn)的度數(shù)都是偶數(shù)。 有向圖：所有頂點(diǎn)的出度等于入度。 混合圖：想辦法把無向邊定向，使所有點(diǎn)出度等于入度。 輸出歐拉回路的方法：DFS,歐拉回路,混合圖中的處理： 無向邊隨意定向，生成一個有向圖，當(dāng)有結(jié)點(diǎn)的出入度之差為奇數(shù)，則不存在歐拉回路。 從一個出度大的點(diǎn)出發(fā)，尋找一條路徑(路徑上的邊是原圖的無向邊) ，中止于出度小的點(diǎn)。然后對這條路徑逆向。 反復(fù)操作直到?jīng)]有出度大的點(diǎn)為止。,Necklace (uva 10054),一串項(xiàng)鏈的珠子有兩種顏色，串起來時要求相鄰顏色一樣。給了一些珠子，判斷是否能串起來。,輸入： 2 5 1 2 2 3 3 4 4 5 5 6 5 2 1 2 2 3 4 3 1 2 4,輸出： Case #1 some beads may be lost Case #2 2 1 1 3 3 4 4 2 2 2,Ouroboros Snake (uva 10040),圓環(huán)上分布著2n個0、1，按順序連續(xù)取n個，就能把0 2n-1個整數(shù)都取到。(0n22),Euler Circuit (uva 10735),在混合圖中判斷是否存在歐拉回路，存在則輸出之。,輸出： 1 3 4 2 5 6 5 4 1 No euler circuit exist,輸入： 2 6 8 1 3 U 1 4 U 2 4 U 2 5 D 3 4 D 4 5 U 5 6 D 5 6 U 4 4 1 2 D 1 4 D 2 3 U 3 4 U,哈密爾頓回路,直接用DFS搜索尋找。,最小生成樹,Prim算法 設(shè)G=(V,E)是無向圖，求它的最小生成樹T=(V,E)的Prim算法為： 從V中任取一結(jié)點(diǎn)放入V； 在所有的端點(diǎn)分別在(V-V)和V中的邊中，選一條權(quán)最小的加入E； 將邊E在(V-V)中的頂點(diǎn)從V中取出放入V； 重復(fù)步驟，直到V與V相等為止。,最小生成樹,構(gòu)造下圖的最小生成樹,U=v0,U=v0,v2,U=v0,v2,v5,U=v0,v2,v5,v3,U=v0,v2,v5,v3,v1,U=v0,v2,v5,v3,v1,v4,Prim 算法數(shù)據(jù)結(jié)構(gòu),1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,圖G,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,圖G,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,圖G,U,U,0 1 2 3 4 5,數(shù)組：lowcost 6 ,數(shù)組：lowcost 6 ,注意：lowcost 0 = 0 lowcost 表示最小距離,0 1 2 3 4 5,最小生成樹,Kruscal算法 把邊按權(quán)值遞減排序，按順序每次添加一條邊，如果產(chǎn)生回路則舍棄。當(dāng)把所有點(diǎn)都連通起來，則得到最小生成樹。,Kruscal 算法的實(shí)例,實(shí)例的執(zhí)行過程,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,圖G,1、初始連通分量：1,2,3,4,5,6 2、反復(fù)執(zhí)行“添加”、“放棄”動作。條件：邊數(shù)不等于 n-1時 邊 動作 連通分量 (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)成回路 (3,4) 放棄 因構(gòu)成回路 (2,3) 添加 1,3,4,5,6,2,算法實(shí)現(xiàn)要點(diǎn): 用并查集的相關(guān)操作：實(shí)現(xiàn)集合的并；判斷新邊的兩端點(diǎn)是否處于同一集合，來確定是否構(gòu)成回路。,最小代價(jià)生成樹,1,2,4,3,5,6,1,5,3,4,2,5,5,Kruscal 算法數(shù)據(jù)結(jié)構(gòu),優(yōu)先隊(duì)列(把所有邊按長度遞增的順序保存在一個表里) 并查集,并查集 (Union-Find Sets),先把每一個對象看作是一個單元素集合，然后按一定順序?qū)⑾嚓P(guān)聯(lián)的元素所在的集合合并。能夠完成這種功能的集合就是并查集。 對于并查集來說，每個集合用一棵樹表示。 它支持以下操作： Unite (Root1, Root2) /并操作 Find (x) /搜索操作（搜索編號