圖論C版課件.ppt

圖論算法c 一對一和一對多的結(jié)構(gòu) 在前邊講解的線性表中 每個元素之間只有一個直接前驅(qū)和一個直接后繼 在樹形結(jié)構(gòu)中 數(shù)據(jù)元素之間是層次關(guān)系 并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關(guān) 但只能和上一層中一個元素相關(guān) 圖結(jié)構(gòu) 是研究數(shù)據(jù)元素之間的多對多的關(guān)系 在這種結(jié)構(gòu)中 任意兩個元素之間可能存在關(guān)系 即結(jié)點之間的關(guān)系可以是任意的 圖中任意元素之間都可能相關(guān) 圖的應用極為廣泛 已滲入到諸如語言學 邏輯學 物理 化學 電訊 計算機科學以及數(shù)學的其它分支 一 圖的定義及其術(shù)語圖 Graph 是由頂點的有窮非空集合和頂點之間邊的集合組成 通常表示為 G V E 其中 G表示一個圖 V是圖G中頂點的集合 E是圖G中邊的集合 對于圖的定義 我們需要明確幾個注意的地方 線性表中我們把數(shù)據(jù)元素叫元素 樹中叫結(jié)點 在圖中數(shù)據(jù)元素我們則稱之為頂點 Vertex 線性表可以沒有數(shù)據(jù)元素 稱為空表 樹中可以沒有結(jié)點 叫做空樹 而圖結(jié)構(gòu)在國內(nèi)大部分的教材中強調(diào)頂點集合V要有窮非空 線性表中 相鄰的數(shù)據(jù)元素之間具有線性關(guān)系 樹結(jié)構(gòu)中 相鄰兩層的結(jié)點具有層次關(guān)系 而圖結(jié)構(gòu)中 任意兩個頂點之間都可能有關(guān)系 頂點之間的邏輯關(guān)系用邊來表示 邊集可以是空的 圖的各種定義 無向邊 若頂點Vi到Vj之間的邊沒有方向 則稱這條邊為無向邊 Edge 用無序偶數(shù)對 Vi Vj 來表示 無向圖 圖中所有頂點間的邊均是無向的 上圖G1是一個無向圖 G1 V1 E1 其中V1 A B C D E1 A B B C C D D A A C 無序?qū)?A B 表示A和B之間的一條邊 Edge 因此 A B 和 B A 代表的是同一條邊 上圖G2是一個無向圖 G2 V2 E2 其中V2 A B C D E2 有向邊 若從頂點Vi到Vj的邊有方向 則稱這條邊為有向邊 也稱為弧 Arc 用有序偶數(shù)對來表示 Vi稱為弧尾 Vj稱為弧頭 有向圖 圖中所有頂點間的邊均是有向的 簡單圖 在圖結(jié)構(gòu)中 若不存在頂點到其自身的邊 且同一條邊不重復出現(xiàn) 則稱這樣的圖為簡單圖 以下兩個則不屬于簡單圖 稀疏圖 稠密圖 權(quán)有很少邊或弧的圖 e n n 的圖稱為稀疏圖 反之稱為稠密圖 權(quán) Weight 與圖的邊和弧相關(guān)的數(shù) 權(quán)可以表示從一個頂點到另一個頂點的距離或耗費 帶權(quán)的圖通常稱為網(wǎng) Network 無向完全圖 在無向圖中 如果任意兩個頂點之間都存在邊 則稱該圖為無向完全圖 含有n個頂點的無向完全圖有n n 1 2條邊 有向完全圖 在有向圖中 如果任意兩個頂點之間都存在方向互為相反的兩條弧 則稱該圖為有向完全圖 含有n個頂點的有向完全圖有n n 1 條邊 假設有兩個圖G1 V1 E1 和G2 V2 E2 如果V2 V1 E2 E1 則稱G2為G1的子圖 Subgraph 圖的頂點與邊之間的關(guān)系 對于無向圖G V E 如果邊 V1 V2 E 則稱頂點V1和V2互為鄰接點 Adjacent 即V1和V2相鄰接 邊 V1 V2 依附 incident 于頂點V1和V2 或者說邊 V1 V2 與頂點V1和V2相關(guān)聯(lián) 頂點V的度 Degree 是和V相關(guān)聯(lián)的邊的數(shù)目 記為TD V 如下圖 頂點A與B互為鄰接點 邊 A B 依附于頂點A與B上 頂點A的度為3 對于有向圖G V E 如果有 E 則稱頂點V1鄰接到頂點V2 頂點V2鄰接自頂點V1 以頂點V為頭的弧的數(shù)目稱為V的入度 InDegree 記為ID V 以V為尾的弧的數(shù)目稱為V的出度 OutDegree 記為OD V 因此頂點V的度為TD V ID V OD V 下圖頂點A的入度是2 出度是1 所以頂點A的度是3 路徑 Path 路徑長度 回路 Cycle 對無向圖G V E 若從頂點vi經(jīng)過若干條邊能到達vj 稱頂點vi和vj是連通的 又稱頂點vi到vj有路徑 對有向圖G V E 從頂點vi到vj有有向路徑 指的是從頂點vi經(jīng)過若干條有向邊 弧 能到達vj 在一條路徑中 若沒有重復相同的頂點 該路徑稱為簡單路徑 第一個頂點和最后一個頂點相同的路徑稱為回路 環(huán) 在一個回路中 若除第一個與最后一個頂點外 其余頂點不重復出現(xiàn)的回路稱為簡單回路 簡單環(huán) 如果G是有向圖 則路徑也是有向的 下圖用紅線列舉頂點B到頂點D的兩種路徑 而頂點A到頂點B就不存在路徑 路徑的長度是路徑上的邊或弧的數(shù)目 第一個頂點到最后一個頂點相同的路徑稱為回路或環(huán) Cycle 右圖用紅線列舉了從頂點B到頂點D的四種不同路徑 連通圖在無向圖G中 如果從頂點V1到頂點V2有路徑 則稱V1和V2是連通的 如果對于圖中任意兩個頂點Vi和Vj都是連通的 則稱G是連通圖 ConnectedGraph 下圖左側(cè)不是連通圖 右側(cè)是連通圖 無向圖中的極大連通子圖稱為連通分量 注意以下概念 首先要是子圖 并且子圖是要連通的 連通子圖含有極大頂點數(shù) 極大 的含義 指的是對子圖再增加圖G中的其它頂點 子圖就不再連通 具有極大頂點數(shù)的連通子圖包含依附于這些頂點的所有邊 在有向圖G中 如果對于每一對Vi到Vj都存在路徑 則稱G是強連通圖 有向圖中的極大強連通子圖稱為有向圖的強連通分量 下圖左側(cè)并不是強連通圖 右側(cè)是 并且右側(cè)是左側(cè)的極大強連通子圖 也是左側(cè)的強連通分量 二 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)比較復雜 其復雜性主要表現(xiàn)在 任意頂點之間可能存在聯(lián)系 無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間的關(guān)系 圖中頂點的度不一樣 有的可能相差很大 若按度數(shù)最大的頂點設計結(jié)構(gòu) 則會浪費很多存儲單元 反之按每個頂點自己的度設計不同的結(jié)構(gòu) 又會影響操作 圖的常用的存儲結(jié)構(gòu)有 鄰接矩陣 鄰接鏈表 十字鏈表 鄰接多重表和邊表 1 二維數(shù)組鄰接矩陣存儲基本思想 對于有n個頂點的圖 用一維數(shù)組vexs n 存儲頂點信息 用二維數(shù)組A n n 存儲頂點之間關(guān)系的信息 該二維數(shù)組稱為鄰接矩陣 在鄰接矩陣中 以頂點在vexs數(shù)組中的下標代表頂點 鄰接矩陣中的元素A i j 存放的是頂點i到頂點j之間關(guān)系的信息 定義intG 101 101 G i j 的值 表示從點i到點j的邊的權(quán)值 定義如下 上圖中的3個圖對應的鄰接矩陣分別如下 0111011 58 3G A 1011G B 0015 2 61100010G C 82 1041100 10 1136411 另外有向圖是有講究的 要考慮入度和出度 頂點V1的入度為1 正好是第V1列的各數(shù)之和 頂點V1的出度為2 正好是第V1行的各數(shù)之和 下面是建立圖的鄰接矩陣的參考程序段 includeusingnamespacestd inti j k e n doubleg 101 101 doublew intmain inti j for i 1 i e for k 1 k i j w 讀入兩個頂點序號及權(quán)值g i j w 對于不帶權(quán)的圖g i j 1g j i w 無向圖的對稱性 如果是有向圖則不要有這句 return0 建立鄰接矩陣時 有兩個小技巧 初始化數(shù)組大可不必使用兩重for循環(huán) 1 如果是int數(shù)組 采用memset g 0 x7f sizeof g 可全部初始化為一個很大的數(shù) 略小于0 x7fffffff 使用memset g 0 sizeof g 全部清為0 使用memset g 0 xaf sizeof g 全部初始化為一個很小的數(shù) 2 如果是double數(shù)組 采用memset g 127 sizeof g 可全部初始化為一個很大的數(shù)1 38 10306 使用memset g 0 sizeof g 全部清為0 2 數(shù)組模擬鄰接表存儲鄰接矩陣看上去是個不錯的選擇 首先是容易理解 第二是索引和編排都很舒服但是我們也發(fā)現(xiàn) 鄰接矩陣適合于結(jié)點數(shù)較少的稠密圖 如果用來表示稀疏圖 則會造成很大的空間浪費 因此我們可以考慮另外一種存儲結(jié)構(gòu)方式 例如把數(shù)組與鏈表結(jié)合一起來存儲 這種方式在圖結(jié)構(gòu)也適用 我們稱為鄰接表 AdjacencyList 基本思想 對圖的每個頂點建立一個單鏈表 存儲該頂點所有鄰接頂點及其相關(guān)信息 每一個單鏈表設一個表頭結(jié)點 第i個單鏈表表示依附于頂點Vi的邊 對有向圖是以頂點Vi為頭或尾的弧 圖的鄰接表存儲法 又叫鏈式存儲法 本來是要用鏈表實現(xiàn)的 但大多數(shù)情況下只要用數(shù)組模擬即可 鄰接表 有向圖 鄰接表的處理方法是這樣 圖中頂點用一個一維數(shù)組存儲 當然 頂點也可以用單鏈表來存儲 不過數(shù)組可以較容易地讀取頂點信息 更加方便 圖中每個頂點Vi的所有鄰接點構(gòu)成一個線性表 由于鄰接點的個數(shù)不確定 所以我們選擇用單鏈表來存儲 若是有向圖 鄰接表結(jié)構(gòu)就是這樣定義的 有向圖的鄰接表 我們先來看下把頂點當弧尾建立的鄰接表 這樣很容易就可以得到每個頂點的出度 但也有時為了便于確定頂點的入度或以頂點為弧頭的弧 我們可以建立一個有向圖的逆鄰接表 此時我們很容易就可以算出某個頂點的入度或出度是多少 判斷兩頂點是否存在弧也很容易實現(xiàn) 對于帶權(quán)值的網(wǎng)圖 可以在邊表結(jié)點定義中再增加一個數(shù)據(jù)域來存儲權(quán)值即可 鄰接表 網(wǎng) 在進行鄰接表的輸入時 可以直接使用鄰接表的定義方式直接輸入 也可由別的輸入方式進行演變 課本上的就是利用邊的頂點及其權(quán)值進行輸入的 以下是用數(shù)組模擬鄰接表存儲的參考程序段 constintN maxn maxn表示圖中最大頂點數(shù)constintE maxe maxe圖中最大邊數(shù)structEdge intu v 邊所鄰接的兩個頂點intw 邊的權(quán)值intnext 邊指針 指向下一條邊的內(nèi)存地址 edge E 靜態(tài)內(nèi)存 用于分配邊inthead N 表頭intnum 內(nèi)存的指針voidinit for inti 0 i E i head i 1 這里為什么要設為 1num 0 voidaddedge intb inte intw edge num u b edge num v e edge num w w edge num next head b head b num intmain num edge 0 scanf d d 兩種方法各有用武之地 需按具體情況 具體選用 例題 求一個有向圖中指定頂點的出度 問題描述 如題 文件輸入 第1行 2個空格分開的整數(shù)n 2 n 200 和m 10 m 20000 分別表示圖的頂點數(shù)和邊數(shù) 第2 m 1行 每行2個空格分開的整數(shù)i j i表示一條邊的起點 j表示終點 第m 2行 1個整數(shù)k 2 k n 表示指定的頂點 文件輸出 只有一行為1個整數(shù) 表示頂點k的出度 樣例輸入 5835454323544142244 樣例輸出 4 2019 12 20 28 可編輯 參考代碼 方法1 鄰接矩陣存儲圖 includeusingnamespacestd inta 201 201 n m ans 0 x voidinit inti j k cin n m for i 1 i j k a j k 1 intmain init cin k for inti 1 i n i if a k i ans cout ans endl 方法2 鄰接表存儲圖 includeusingnamespacestd structEdge intto next w 20005 inth Maxn 0 i x y z n e k cnt ans 0 voidAddEdge intx inty cnt w cnt to y w cnt next h x h x cnt intmain cin n e 讀入頂點數(shù)目和邊數(shù)for i 1 i x y AddEdge x y 建圖cin k for intp h k p 0 p w p next ans cout ans endl 第二節(jié)圖的遍歷 一 深度優(yōu)先與廣度優(yōu)先遍歷從圖中某一頂點出發(fā)系統(tǒng)地訪問圖中所有頂點 使每個頂點恰好被訪問一次 這種運算操作被稱為圖的遍歷 為了避免重復訪問某個頂點 可以設一個標志數(shù)組visited i 未訪問時值為false 訪問一次后就改為true 圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法 兩者的時間效率都是O n n 1 深度優(yōu)先遍歷深度優(yōu)先搜索 DepthFirstSearch DFS 遍歷類似樹的先序遍歷 是樹的先序遍歷的推廣 1算法思想設初始狀態(tài)時圖中的所有頂點未被訪問 則 從圖中某個頂點vi出發(fā) 訪問vi 然后找到vi的一個鄰接頂點vi1 從vi1出發(fā) 深度優(yōu)先搜索訪問和vi1相鄰接且未被訪問的所有頂點 轉(zhuǎn) 直到和vi相鄰接的所有頂點都被訪問為止 繼續(xù)選取圖中未被訪問頂點vj作為起始頂點 轉(zhuǎn) 1 直到圖中所有頂點都被訪問為止 例如對右邊的這個無向圖深度優(yōu)先遍歷 假定先從1出發(fā)程序以如下順序遍歷 1 2 5 然后退回到2 退回到1 從1開始再訪問未被訪問過的點3 3沒有未訪問的鄰接點 退回1 再從1開始訪問未被訪問過的點4 再退回1 起點1的所有鄰接點都已訪問 遍歷結(jié)束 下面給出的深度優(yōu)先遍歷的參考程序 假設圖以鄰接表存儲voiddfs inti 圖用數(shù)組模擬鄰接表存儲 訪問點i visited i true 標記為已經(jīng)訪問過for intj 1 j num i j 遍歷與i相關(guān)聯(lián)的所有未訪問過的頂點if visited g i j dfs g i j 主程序如下 intmain memset visited false sizeof visited for inti 1 i n i 每一個點都作為起點嘗試訪問 因為不是從任何 一點開始都能遍歷整個圖的 例如下面的兩個圖 if visited i dfs i return0 廣度優(yōu)先搜索BFS 廣度優(yōu)先搜索 BreadthFirstSearch BFS 遍歷類似樹的按層次遍歷的過程 1算法思想設初始狀態(tài)時圖中的所有頂點未被訪問 則 從圖中某個頂點vi出發(fā) 訪問vi 訪問vi的所有相鄰接且未被訪問的所有頂點vi1 vi2 vim 以vi1 vi2 vim的次序 以vij 1 j m 依此作為vi 轉(zhuǎn) 繼續(xù)選取圖中未被訪問頂點vk作為起始頂點 轉(zhuǎn) 直到圖中所有頂點都被訪問為止 下圖是有向圖的廣度優(yōu)先搜索遍歷示例 淺色箭頭 上述圖的BFS次序是 v1 v2 v4 v3 v5 用廣度優(yōu)先搜索算法遍歷圖與深度優(yōu)先搜索算法遍歷圖的唯一區(qū)別是鄰接點搜索次序不同 因此 廣度優(yōu)先搜索算法遍歷圖的總時間復雜度為O n e 圖的遍歷可以系統(tǒng)地訪問圖中的每個頂點 因此 圖的遍歷算法是圖的最基本 最重要的算法 許多有關(guān)圖的操作都是在圖的遍歷基礎之上加以變化來實現(xiàn)的 例題 無向圖的BFS 問題描述 一個無向圖 從指定頂點出發(fā)進行BFS 求遍歷得到的頂點序 文件輸入 第1行 2個空格分開的整數(shù)n 2 n 200 和m 10 m 20000 分別表示圖的頂點數(shù)和邊數(shù) 第2 m 1行 每行2個空格分開的整數(shù)i j i表示一條邊的起點 j表示終點 第m 2行 1個整數(shù)k 1 k n 表示指定的頂點 文件輸出 只一行頂點序 要求在同一層上 頂點序號從小到大輸出 includeusingnamespacestd inta 101 101 f 101 q 101 n m i st voidinit inti j x y cin n m memset f 0 sizeof f for i 1 i x y a x y 1 a y x 1 cin st voiddfs inti 深搜DFS intj cout i f i 1 for j 1 j n j if f j 0 二 歐拉圖 1 歐拉路 歐拉路徑 圖G中每條邊經(jīng)過一次且僅一次的路徑稱作歐拉路徑 如下圖中存在一條從頂點1到頂點6的歐拉路 一筆畫問題其實本質(zhì)上就是判斷一個圖是否存在歐拉路 無向圖歐拉路存在的充要條件 圖是連通的 圖中有且僅有0個或2個度數(shù)為奇數(shù)的點 若存在2個奇點 則歐拉路一定是從一個奇點出發(fā) 以另一個奇點結(jié)束 2 歐拉回路 圖G中每條邊經(jīng)過一次且僅一次的回路稱作歐拉回路 著名的柯尼斯堡七橋問題 圖論起源 本質(zhì)上就是討論一個圖的歐拉回路問題 一個無向圖有歐拉回路的必要條件是 圖是連通的 圖中所有點的度均為偶數(shù) 求歐拉路的算法很簡單 使用深度優(yōu)先遍歷即可 根據(jù)一筆畫的兩個定理 如果尋找歐拉回路 對任意一個點執(zhí)行深度優(yōu)先遍歷 找歐拉路 則對一個奇點執(zhí)行DFS 時間復雜度為O m n m為邊數(shù) n是點數(shù) 以下是尋找一個圖的歐拉路的算法實現(xiàn) 樣例輸入 第一行n m 有n個點 m條邊 以下m行描述每條邊連接的兩點 551223344551樣例輸出 歐拉路或歐拉回路154321 參考程序 Euler cpp include includeusingnamespacestd definemaxn101intg maxn maxn 此圖用鄰接矩陣存儲intdu maxn 記錄每個點的度 就是相連的邊的數(shù)目intcircuit maxn 用來記錄找到的歐拉路的路徑intn e circuitpos i j x y start voidfind circuit inti 這個點深度優(yōu)先遍歷過程尋找歐拉路 intj for j 1 j n j if g i j 1 從任意一個與它相連的點出發(fā) g j i g i j 0 find circuit j circuit circuitpos i 記錄下路徑 intmain memset g 0 sizeof g cin n e for i 1 i x y g y x g x y 1 du x 統(tǒng)計每個點的度du y start 1 如果有奇點 就從奇點開始尋找 這樣找到的就是for i 1 i n i 歐拉路 沒有奇點就從任意點開始 if du i 2 1 這樣找到的就是歐拉回路 因為每一個點都是偶點 start i circuitpos 0 find circuit start for i 1 i circuitpos i cout circuit i cout endl return0 注意以上程序具有一定的局限性 對于下面這種情況它不能很好地處理 上圖具有多個歐拉回路 而本程序只能找到一個回路 讀者在遇到具體問題時 還應對程序作出相應的修改 三 哈密爾頓環(huán)歐拉回路是指不重復地走過所有路徑的回路 而哈密爾頓環(huán)是指不重復地走過所有的點 并且最后還能回到起點的回路 哈密頓通路 回路 與哈密頓圖 Hamilton圖 通過圖G的每個結(jié)點一次 且僅一次的通路 回路 就是哈密頓通路 回路 存在哈密頓回路的圖就是哈密頓圖 美國圖論數(shù)學家奧勒在1960年給出了一個圖是哈密爾頓圖的充分條件 對于頂點個數(shù)大于2的圖 如果圖中任意兩點度的和大于或等于頂點總數(shù) 那這個圖一定是哈密頓圖 閉合的哈密頓路徑稱作哈密頓圈 含有圖中所有頂點的路徑稱作哈密頓路徑 例題1 哈密頓路問題 問題描述 郵遞員在送信時 為了節(jié)省路途 自己規(guī)定 每次總是從n個村子中選擇其中一個合適的村子出發(fā) 途經(jīng)每個村子僅且經(jīng)過一次 送完所有的信 已知各個村子的道路連通情況 請你幫郵遞員選擇一條合適的路線 文件輸入 第1行 整數(shù)n 2 n 200 村子的個數(shù) 接下來是一個n n的0 1矩陣 每2個數(shù)之間有1個空格 表示n個村子的連通情況 如 a i j 1 表示第i和第j個村子之間有路可走 如果a i j 0 表示他們之間無路可走 文件輸出 只有一行為1個整數(shù)表示可行的方案總數(shù) include includeusingnamespacestd inta 201 201 visit 201 found n sum voidinit inti j scanf d intmain inti init found 0 sum 0 for i 1 i n i memset visit 0 sizeof visit visit i 1 dfs i 1 if found 0 printf d 0 elseprintf d sum return0 使用簡單的深度優(yōu)先搜索 就能求出一張圖中所有的哈密爾頓環(huán) 下面給出一段參考程序 include includeusingnamespacestd intstart length x n boolvisited 101 v1 101 intans 101 num 101 intg 101 101 voidprint inti for i 1 i length i cout ans i cout endl voiddfs intlast inti 圖用數(shù)組模擬鄰接表存儲 訪問點i last表示上次訪問的點 visited i true 標記為已經(jīng)訪問過v1 i true 標記為已在一張圖中出現(xiàn)過ans length i 記錄下答案for intj 1 j num i j if g i j x 這里是回溯過程 注意v1的值不恢復 intmain memset visited false sizeof visited memset v1 false sizeof v1 for x 1 x n x 每一個點都作為起點嘗試訪問 因為不是從任何一點開始都能找過整個圖的if v1 x 如果點x不在之前曾經(jīng)被訪問過的圖里 length 0 定義一個ans數(shù)組存答案 length記答案的長度 dfs 0 x return0 上機練習 1 珍珠BEAD 問題描述 有n顆形狀和大小都一致的珍珠 它們的重量都不相同 n為整數(shù) 所有的珍珠從1到n編號 你的任務是發(fā)現(xiàn)哪顆珍珠的重量剛好處于正中間 即在所有珍珠的重量中 該珍珠的重量列 n 1 2位 下面給出將一對珍珠進行比較的辦法 給你一架天平用來比較珍珠的重量 我們可以比出兩個珍珠哪個更重一些 在作出一系列的比較后 我們可以將某些肯定不具備中間重量的珍珠拿走 例如 下列給出對5顆珍珠進行四次比較的情況 1 珍珠2比珍珠1重2 珍珠4比珍珠3重3 珍珠5比珍珠1重4 珍珠4比珍珠2重根據(jù)以上結(jié)果 雖然我們不能精確地找出哪個珍珠具有中間重量 但我們可以肯定珍珠1和珍珠4不可能具有中間重量 因為珍珠2 4 5比珍珠1重 而珍珠1 2 3比珍珠4輕 所以我們可以移走這兩顆珍珠 寫一個程序統(tǒng)計出共有多少顆珍珠肯定不會是中間重量 輸入格式 輸入文件第一行包含兩個用空格隔開的整數(shù)N和M 其中1 N 99 且N為奇數(shù) M表示對珍珠進行的比較次數(shù) 接下來的M行每行包含兩個用空格隔開的整數(shù)x和y 表示珍珠x比珍珠y重 輸出格式 輸出文件僅一行包含一個整數(shù) 表示不可能是中間重量的珍珠的總數(shù) 輸入樣例 BEAD IN542143514