【文章內(nèi)容簡介】 個新圖……。以此類推，不斷地從新圖中找到度為2的點，然后將其相應(yīng)的兩條邊中是多邊形的邊添加入圖C中，接著從圖中刪除這個點。如此反復(fù)，直到圖中不存在度為2的點。然后把圖中剩下的邊中，是多邊形的邊的添加到圖C中。最后，圖C便是要求的原始多邊形。樣例的模擬過程如下：左邊是圖G的變化過程右邊是圖C的變化過程圖32還存在一個問題沒有解決：如何判斷移除的邊是否是原多邊形的邊呢？首先考慮一下，一條邊（Hi, Hj）什么時候才會被移除。一條邊（Hi, Hj）當(dāng)且僅當(dāng)成為某個多邊形的邊時，它才有可能被移除。如果（Hi, Hj）是原始多邊形的一條對角線，當(dāng)且僅當(dāng)哈密頓回路上從Hi+1到Hj1的頂點都已經(jīng)被刪除，（Hi, Hj）才有可能成為新多邊形的邊。如何判斷從Hi+1到Hj1的頂點是否已經(jīng)被刪除呢？這時構(gòu)造的附加圖C就起到了作用！若從Hi+1到Hj1的頂點已經(jīng)被刪除，則這些頂點在原多邊形上相應(yīng)的邊都已經(jīng)添加到圖C中，Hi到Hj在圖C中一定存在一條路徑。因此判斷一條移除的邊（Hi, Hj）是否是對角線，只需要判斷在圖C中Hi和Hj是否連通。值得注意的是，當(dāng)圖C中已經(jīng)有了n 1條邊時，剩下的那條邊會被判斷成對角線，但此時已經(jīng)能夠確定多邊形頂點的標(biāo)號序列了。算法的大致輪廓已經(jīng)清楚了，下面為算法選擇合適的數(shù)據(jù)結(jié)構(gòu)：a. 圖G的存儲結(jié)構(gòu)：由于圖G是稀疏圖，可以用鄰接表存儲，用來查找度為2的頂點與哪些邊相連。還要用一個哈希表存下所有的邊，用于查找任意兩個點是否相連。設(shè)一條邊為(u, v)，哈希表可以用作為關(guān)鍵字，哈希函數(shù)為，P為大質(zhì)數(shù)。這樣在保證查找復(fù)雜度仍然是O(1)的情況下，存儲空間比鄰接矩陣小了很多。b. 枚舉度為2的結(jié)點：很容易想到用最小堆來找出度為2的頂點，不過這樣的復(fù)雜度稍稍高了一點。由于頂點的度數(shù)只減少不增加，而且真正有效的度數(shù)只有1和2，所以可以建立四個桶來替代堆。將頂點按度數(shù)分別放到四個不同的桶中：度數(shù)為0、度數(shù)為度數(shù)為度數(shù)大于2。在每個桶中用雙向鏈接表存儲下不同的結(jié)點。當(dāng)一個頂點的度數(shù)被修改的時候，從原桶中刪除，放到相應(yīng)的桶中。在雙向鏈表中的插入和刪除結(jié)點，時間復(fù)雜度都是O(1)。而因為每個結(jié)點的度數(shù)是不斷減少的，所以每個結(jié)點最多進(jìn)出每個桶一次。綜上所述，在這些桶中查找和調(diào)整一個度為2的結(jié)點所需的時間復(fù)雜度為O(1)。c. 在圖C中添加邊，判斷任意兩點的連通性：可以采用并查集來實現(xiàn)邊的添加（即將兩個連通子圖合并）和判斷點的連通性（即判斷兩個點是否在同一個連通子圖中）。添加一條邊和判斷一對點的連通性兩種操作的均攤復(fù)雜度為O(α(n))。下面是對算法二的總括：算法二1． 根據(jù)每個頂點的度數(shù)將n個頂點放到四個桶中。初始化附加圖C。2． 如果存在一個度數(shù)為2的頂點u，則接下來執(zhí)行第3步，否則轉(zhuǎn)步驟6。3． 在鄰接表中找到和u相連的兩個頂點為v1和v2。4． 首先判斷(u,v1)、(u,v2)是否為虛邊。若不是虛邊，用并查集檢查其是否為對角線。最后將是多邊形的邊插入到圖C中。5． 將頂點u標(biāo)記為不可用。用哈希表檢查邊(v1,v2)是否存在圖G中。如果邊(v1,v2)不存在，則添加一條虛邊(v1,v2)，v1和v2的度數(shù)不變；否則將v1和v2的度數(shù)減一。若v1或v2修改后的度數(shù)不符合所在桶的性質(zhì)，則進(jìn)行調(diào)整。然后轉(zhuǎn)到步驟2。6． 找到殘圖G中所有度數(shù)為1的頂點，一一檢查這些頂點相應(yīng)的邊在附加圖C中的連通性，把非對角線和虛邊的邊插入到圖C中。7． 遍歷圖C得到原始多邊形頂點的標(biāo)號順序。在每個頂點刪除時，最多添加一條虛邊，因此原始邊和虛邊的總數(shù)仍然是O(n)的級別?，F(xiàn)在分析一下時間復(fù)雜度：步驟3中，每個頂點最多查找一次，因此復(fù)雜度為邊數(shù)，即O(n)；步驟4和步驟6中，用并查集查找和插入的均攤時間復(fù)雜度為O(nα(n))；步驟5中，用哈希表查找一條邊的復(fù)雜度為O(1)，邊的插入和桶的調(diào)整也是O(1)，一共進(jìn)行頂點數(shù)次，所以時間復(fù)雜度為O(n)。綜上所述，算法二的復(fù)雜度為O(nα(n))。算法二的時間復(fù)雜度已經(jīng)十分低了。但追求無止境的我們不能淺嘗輒止，因為算法二仍存在需待改進(jìn)的地方：編程復(fù)雜度實在太高了！算法二雖然已經(jīng)較為充分的挖掘出問題的各種特性，但在利用這些特性時，是通過不斷分解成子問題然后一一擊破的方法來實現(xiàn)的。我們不禁提出一個問題：是否能找到一種綜合的方法，將所有特性一起利用，使得解決方法既簡便又高效呢？ DFS樹反映的問題特性回到多邊形所在的平面圖上。若按深度優(yōu)先來遍歷平面圖，當(dāng)經(jīng)過一條對角線時，平面圖便被分成了兩個部分。由于是深度優(yōu)先遍歷，那么在這兩部分剩下的點中，有一部分的點會被優(yōu)先遍歷到。因此可以模仿DFS尋找塊的算法，利用頂點的遍歷順序和low函數(shù)來判斷邊的性質(zhì)。首先定義一下DFS中需要用到的兩個函數(shù)：dfn[v]表示v是深搜中第幾個被遍歷到的。 其中w1表示v的兒子結(jié)點，w2表示DFS樹中異于v的父親結(jié)點的其他祖先結(jié)點。接下來分情況討論如何用dfn和low函數(shù)判斷一條邊的性質(zhì)：考慮DFS樹上的一條邊(u, v)，其中u是v的父親結(jié)點。由于圖G是一個塊，因此每個點的兒子個數(shù)不會超過2。根據(jù)v的度數(shù)分下面四種情況：uvw圖34yxuv圖331．v的兒子數(shù)為0：意味著(u,v)是原始多邊形的邊。否則的話，v所有的祖先結(jié)點都在(u,v)的一側(cè)，而另一側(cè)一定仍有點存在，與兒子數(shù)為0矛盾。令x是與v直接相連的祖先結(jié)點中dfn值最小的一個結(jié)點，那么(x,v)一定也是原始多邊形的邊。略證：如圖33，另(x,v)為多邊形的邊。v不是x的父親結(jié)點，說明x一定先于u被遍歷到，而且x是u的祖先結(jié)點。也就是說，x到u存在一條路徑，路徑上的邊都是由DFS樹上的邊組成。令y為異于x和u，而與v相連的點。由于圖G是平面圖，那么y一定在x到u路徑上。因此y一定后于x被遍歷，即dfn[y]小于dfn[x]。所以x一定是與v相連的祖先結(jié)點中dfn值最小的。2．v的兒子數(shù)為1，且u為DFS樹的根：易知，(u, v)一定是多邊形的邊。3．v的兒子數(shù)為1，且u不是DFS樹的根：令w為v惟一的兒子。若low[w]大于等于dfn[u]，則(u, v)為多邊形的對角線。因為(u, v)將平面分成了兩部分，w和其子樹結(jié)點是遍歷不到另一部分的，如圖34。令x是與v直接相連的祖先結(jié)點中dfn值最小的一個結(jié)點，那么(x, v)一定是原始多邊形的邊（證明同情況1中的分析）。而與v相連的另一條多邊形的邊可以在遍歷w時找到。若low[w]小于dfn[u]，則(u, v)是多邊形的邊，而與v相連的另一條多邊形的邊可以在遍歷w時找到。4．v的兒子數(shù)為2，則與v相連的兩條多邊形的邊可以在遍歷兒子結(jié)點時找到?？紤]上述四種情況已經(jīng)能夠判斷圖G中所有邊的性質(zhì)了。因此只需要對圖G進(jìn)行一次深度優(yōu)先遍歷，就能確定多邊形頂點的標(biāo)號順序。所以算法三的時間復(fù)雜度為線性的——O(n)！ 小結(jié)上述三種方法都是建立在同一個模型上的，不同的方法對模型性質(zhì)挖掘的深度不同也就決定了不同的時間復(fù)雜度。算法一運用了定義法，利用對角線將多邊形劃分成兩部分的性質(zhì)找到多邊形中所有的對角線。而在算法二的設(shè)計過程中，發(fā)現(xiàn)了每次刪除多邊形的一個角時仍是一個多邊形，也就是找到了子問題的相似性，這樣就可以不斷地縮小問題的規(guī)模。算法二還體現(xiàn)了一種化歸的思想，將未知問題分成幾個步驟（或者子問題），每個步驟都是我們熟知的，因此可以為每一步選擇最好的算法。由于每個子問題都解決了，原問題也就迎刃而解?？梢哉f方法二是一種分析法。算法三體現(xiàn)了一種綜合思想，不是單獨考慮每一條邊的連通性，而是從全局考慮，發(fā)現(xiàn)了多邊形的邊和對角線在DFS樹中的區(qū)別。因此算法三的設(shè)計一氣呵成，體現(xiàn)了圖論中一種“序”的優(yōu)美性。三種不同的方法也給了我們不同的啟示：定義法告訴我們，當(dāng)找不到問題思考的方向時，可以考慮從問題最基本的性質(zhì)入手