算法合集之圖論的基本思想及方法(編輯修改稿)
2024-11-12 20:30 本頁面
【文章內(nèi)容簡介】 并集包含所有 E中的元素。 可以發(fā)現(xiàn)，圖 G中從最高點(diǎn)到最低點(diǎn)的路徑對(duì)應(yīng)了 E的一個(gè)鏈。 目標(biāo)的轉(zhuǎn)化 ? 直接計(jì)算鏈的最少個(gè)數(shù) ——與網(wǎng)絡(luò)流沒有差別 ? 唯有 ——繼續(xù)轉(zhuǎn)化目標(biāo) 目標(biāo)的轉(zhuǎn)化 ? 鏈和反鏈的計(jì)數(shù)滿足下列關(guān)系： Dilworth定理 令 (E, ≤)是一個(gè)有限偏序集，并令 LA是 E中最大反鏈的大小， SC是將 E劃分成最少的鏈的個(gè)數(shù)。在 E中，有 LA = SC。 求 E中最長反鏈的大小 ? 目標(biāo)最終轉(zhuǎn)化為： 求最長的反鏈 由偏序集 E的定義可以知道： 偏序集 E中的反鏈對(duì)應(yīng)著圖 G中的一些邊，其中任意兩條邊之間都不能互達(dá)。 右圖橙色線段便是樣例的最長反鏈 如果用一條線將最長反鏈所對(duì)應(yīng)的邊從左到右連起來 那么這條線不會(huì)與平面圖中的其它邊相交 ！ 這些線段滿足如下性質(zhì)： 求最長的反鏈 換句話說， 將最長反鏈所對(duì)應(yīng)的邊從左到右排列好，相鄰的兩條邊一定是在同一個(gè)域（閉曲面）中。 （結(jié)論一） 所謂域，是指由從極高點(diǎn)到極低點(diǎn)的兩條獨(dú)立路徑圍成的一個(gè)曲面，在這個(gè)曲面里沒有其他的點(diǎn)和邊。 極高點(diǎn) 極低點(diǎn) 左邊界 右邊界 求最長的反鏈 令 f(x)表示圖 G中在邊 x左邊的平面區(qū)域中以 x結(jié)尾的最長反鏈的長度。 由結(jié)論一可以用遞推方法計(jì)算最長反鏈： 求最長的反鏈 設(shè) x在某個(gè)域 F的右邊界上，有遞推式： f (x) = max{ f (y) } + 1 (y屬于 F的左邊界） 遞推式 (1) f (y) f (x) = f (y) + 1 A B C D 因此只需要將 所有的域 求出來，然后按照 一定的順序 ，在每個(gè)域上運(yùn)用遞推式 (1)求解每條邊 的 f 函數(shù)。 一定的順序 求最長的反鏈 遞推的順序 一定的順序 如何確定遞推的順序呢？ 一個(gè)域能夠進(jìn)行遞推的前提條件 ——它左邊界上的邊的 f 函數(shù)都已經(jīng)求出 以此可以確定遞推順序：若域 B左邊界上的某條邊在域 A的右邊界上，則 A一定先于 B進(jìn)行遞推。 A B A B 先于 注意到，題目中的輸入文件格式滿足： 對(duì)于任意頂點(diǎn)，和它相鄰的點(diǎn)已經(jīng)從左到右排好序。 因此很容易想到一個(gè)方法，能夠按照遞推順序找到所有的域！ DFS深度優(yōu)先遍歷 算法的選擇 找到了遞推關(guān)系，接下來只需要選擇合適的算法求出圖 G中所有的域來進(jìn)行遞推。 算法設(shè)計(jì) ——DFS 對(duì)圖 G進(jìn)行深度優(yōu)先遍歷，圖 G中的頂點(diǎn)在遍歷中有三種狀態(tài)： 一開始，所有點(diǎn)都處于
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1