劉汝佳黑書學(xué)習(xí)指導(dǎo).ppt

算法藝術(shù)與信息學(xué)競(jìng)賽 教學(xué)幻燈片,算法圖論 學(xué)習(xí)指導(dǎo),聲明,本系列教學(xué)幻燈片屬于劉汝佳、黃亮著算法藝術(shù)與信息學(xué)競(jìng)賽配套幻燈片 本幻燈片可從本書blog上免費(fèi)下載，即使您并未購(gòu)買本書. 若作為教學(xué)使用，歡迎和作者聯(lián)系以取得技術(shù)支持，也歡迎提供有不同針對(duì)性的修改版本，方便更多人使用 有任何意見(jiàn)，歡迎在blog上評(píng)論 Blog地址：,內(nèi)容介紹,一、基本概念 二、圖搜索 (重點(diǎn)) 三、DAG 四、連通性問(wèn)題 (重點(diǎn), 中難) 五、道路和回路 六、最短路 (重點(diǎn), 中難) 七、最小生成樹(shù) (重點(diǎn)) 八、最大流問(wèn)題 (重點(diǎn), 偏難) 九、最小費(fèi)用流 (重點(diǎn), 偏難) 十、匹配 (重點(diǎn), 偏難) 十一、圖論難解問(wèn)題 (偏難),一、基本概念,圖的基本概念(1),圖、簡(jiǎn)單圖、圖形表示 結(jié)點(diǎn)、弧、鄰接、關(guān)聯(lián)、度數(shù) 子圖、導(dǎo)出子圖 平面圖、歐幾里得圖、三角形不等式 同構(gòu) 路徑、圈、不相交路、邊不相交路 連通、連通分量 樹(shù)和森林 完全圖和補(bǔ)圖、團(tuán) 稀疏圖和稠密圖,圖的基本概念(2),二分圖(二部圖) 相交圖、區(qū)間圖 有向圖、DAG 帶權(quán)圖、網(wǎng)絡(luò) 圖的ADT, 圖IO的ADT 鄰接矩陣、鄰接表和前向星表示 圖例 : 了解即可 : 需要深入理解 : 需要非常熟悉, 能寫出程序,二、圖搜索,圖搜索,寬度優(yōu)先遍歷: 全部?jī)?nèi)容應(yīng)熟練掌握. 深度優(yōu)先遍歷 基本的DFS-VISIT: 顏色和時(shí)間戳 嵌套區(qū)間定理: 推導(dǎo)+直觀理解 (重點(diǎn)) 白色路徑定理: 直觀理解 (可選, 較難) 邊分類規(guī)則: 直觀理解 邊分類算法: 程序?qū)崿F(xiàn)和復(fù)雜度分析 (重點(diǎn)) 無(wú)向圖只有T邊和B邊: 證明和分類算法 使用pre和post數(shù)組的DFS實(shí)現(xiàn)(重點(diǎn)),三、DAG的算法,DAG的算法,DAG的充要條件: 無(wú)B邊 (證明和直觀理解) 拓?fù)渑判?(熟練掌握) 基于DFS的算法 基于隊(duì)列的算法 關(guān)鍵路徑 PT圖 PERT圖 本講內(nèi)容比較簡(jiǎn)單, 建議全部理解,四、連通性問(wèn)題,連通性問(wèn)題,提醒: 本講比較難, 但算法非常巧妙 SCC劃分 G和GT的SCC相同: 證明和直觀理解 SCC構(gòu)成DAG: 證明和直觀理解 Kosaraju算法: 按f遞減順序DFS轉(zhuǎn)置圖(重點(diǎn)) Tarjan/Gabow: 用棧保留結(jié)點(diǎn), 延遲輸出(難) Tarjan算法: 用LOW測(cè)試輸出條件 Gabow算法: 用棧保留當(dāng)前路徑,連通性問(wèn)題,割頂和橋的判定(重點(diǎn)) 無(wú)向圖的LOW函數(shù) 割頂條件和割頂判定算法 橋條件和橋判定算法 BCC劃分,五、道路和回路,道路和回路,歐拉回路和道路 充要條件 套圈算法及其簡(jiǎn)潔實(shí)現(xiàn) 中國(guó)郵路問(wèn)題 主算法: 倍邊+歐拉回路 權(quán)值: SSSP預(yù)處理 配對(duì): 二分圖最佳匹配預(yù)處理,六、最短路,最短路,SSSP問(wèn)題 一般SSSP算法, 包括正確性證明 (重難點(diǎn)) dijkstra算法的堆實(shí)現(xiàn) (重點(diǎn)) Bellman-ford算法和差分約束系統(tǒng) (重點(diǎn)) Gabow的變尺度算法 (了解即可) APSP問(wèn)題 矩陣乘法算法 floyd-warshall算法, 包括路徑輸出 (重點(diǎn)) Johnson算法, 包括正確性證明 (重點(diǎn)),七、最小生成樹(shù),最小生成樹(shù),一般MST算法: 正確性證明 經(jīng)典MST算法 Boruvka算法 Prim算法 Kruskal算法 其他問(wèn)題 (了解) MST唯一性判定 瓶頸生成樹(shù),八、最大流問(wèn)題,最大流問(wèn)題,基本概念 流網(wǎng)絡(luò)定義、流的三個(gè)性質(zhì) 結(jié)點(diǎn)集的流記號(hào)、運(yùn)算和凸性 相反方向的流取消操作、循環(huán)流、流分解定理 Ford-Fulkerson方法 殘量網(wǎng)絡(luò)、增廣路、切割與流的關(guān)系 最大流的兩個(gè)等價(jià)條件和證明 基本的Ford-Fulkerson方法和復(fù)雜度分析 Edmond-Karp算法 (重點(diǎn)) 關(guān)于d值的單調(diào)性引理、關(guān)鍵弧引理及其證明 (難點(diǎn)) Edmond-Karp算法的時(shí)間復(fù)雜度及其證明,最大流問(wèn)題,預(yù)流推進(jìn)算法 預(yù)流的定義, push和relabel過(guò)程 高度函數(shù)中st的值和性質(zhì): 起點(diǎn)不能太高 (重點(diǎn)) push、relabel和初始化的算法步驟 正確性證明 引理1: 兩個(gè)操作至少一個(gè)能執(zhí)行 引理2、3: h函數(shù)維持性質(zhì)且每次relabel至少增加1 引理4: 殘量網(wǎng)絡(luò)中s到t始終不存在通路 時(shí)間復(fù)雜度分析(難) discharge操作和relabel-to-front算法 (難) 最高標(biāo)號(hào)預(yù)流推進(jìn)算法,最大流問(wèn)題,應(yīng)用舉例 多源多匯問(wèn)題 頂點(diǎn)容量 有環(huán)轉(zhuǎn)無(wú)環(huán) 無(wú)向變有向 可行流 二分圖最大匹配,九、最小費(fèi)用流問(wèn)題,最小費(fèi)用流問(wèn)題,最小費(fèi)