【文章內(nèi)容簡(jiǎn)介】 Star星形表示法就是對(duì)弧表的缺點(diǎn)的改進(jìn)，使之可以通過起點(diǎn)或終點(diǎn)定位邊。由于很多時(shí)候，算法只需事先知道起點(diǎn)，通過枚舉邊擴(kuò)展，而不需要事先知道終點(diǎn)；如圖的遍歷，松弛操作。按定位方式，又分前向星形(forwards star)與反向星形(reverse star)。前向星形：通過起點(diǎn)定位邊。反向星形：通過終點(diǎn)定位邊。實(shí)際上，反向星形幾乎沒用。故本文只討論前向星形。通常有兩種方法實(shí)現(xiàn)這種對(duì)弧表改進(jìn)：邊排序法，鏈表法。邊排序法：把弧表按起點(diǎn)為第一關(guān)鍵字，終點(diǎn)為第二關(guān)鍵字來排序。排序用不用額外空間的快速排序O(mlogm)或用額外空間O(m)的計(jì)數(shù)排序O(m)均可。之后用數(shù)組last(u)記錄以結(jié)點(diǎn)u為起點(diǎn)的最后一條邊的編號(hào)，并規(guī)定last(0)=0。這樣以結(jié)點(diǎn)u為起點(diǎn)的邊編號(hào)就是last(u1)+1到last(u)。有權(quán)圖的例子：作為起點(diǎn)的點(diǎn)012345最后邊的編號(hào)023468編號(hào)12345678起點(diǎn)11234455終點(diǎn)23423534權(quán)值89640367鏈表法：給每條邊(u,v)加一個(gè)前趨，表示以u(píng)為起點(diǎn)的邊鏈表的前一條邊。直觀的講，就是將相同結(jié)點(diǎn)的邊用鏈表串起來。last(u)存以u(píng)為起點(diǎn)的最后一條邊的編號(hào)。有權(quán)圖的例子：作為起點(diǎn)的點(diǎn)12345最后邊的編號(hào)65278編號(hào)012345678起點(diǎn)nil53412145終點(diǎn)nil42524333權(quán)值nil74386906前趨nil00000431星形表示法的優(yōu)點(diǎn)是占用的存貯空間較少。一般圖都適用。邊排序法的優(yōu)點(diǎn)是已知起點(diǎn)和終點(diǎn)的情況下可以精確定位邊，容易在起點(diǎn)定位的范圍內(nèi)二分查找終點(diǎn)，在反向邊的定位中常用；缺點(diǎn)是代碼麻煩，時(shí)間抑或空間上都有額外開銷。鏈表法的優(yōu)點(diǎn)很多，不僅代碼簡(jiǎn)單，而且沒有太多的時(shí)空開銷，對(duì)于反向邊的定位只要多加一個(gè)數(shù)據(jù)項(xiàng)紀(jì)錄下反向邊即可；除了終點(diǎn)定位性，幾乎沒缺點(diǎn)。參考文獻(xiàn)：[1]謝金星，清華大學(xué)數(shù)學(xué)科學(xué)系網(wǎng)絡(luò)優(yōu)化講義~jxie/courses/netopt[2]劉汝佳，黃亮，算法藝術(shù)與信息學(xué)競(jìng)賽，P60. 圖的遍歷 Traveling in graph. 深度優(yōu)先搜索 Depth first search (DFS). 概念. 求無向連通圖中的橋 Finding bridges in undirected graph在無向連通的條件下，邊是橋的充要條件是：；。圈是由一條后向邊(u,v)與DFS樹中u到v的路徑組成。也就是說u到v的路徑上的邊都不可能是橋，應(yīng)該給以標(biāo)記。記f(x)為x與其子孫的后向邊所連到的最老祖先(深度最淺)，表示x 到f(x) 上的邊均不為橋。然而維護(hù)f(x)比較麻煩，其實(shí)只要知道f(x)的拓?fù)湫驍?shù)就可以了。所謂拓?fù)湫驍?shù)就是滿足兒子的序數(shù)總比父親大的一個(gè)編號(hào)方式。這個(gè)拓?fù)湫?，常用使用深度d，或者使用時(shí)間戳(TimeStamp) DFN（DFS訪問的次序）。下面以深度為例：記，在DFS樹中從x開始通過前向弧和后向弧所能到達(dá)的最小的d。有以下的動(dòng)態(tài)規(guī)劃：這里：，記錄d(x)2. d(y)自己發(fā)出去的后向邊所達(dá)到的深度。3. g(c)就是其子孫中的g最小值。最后，若g(x)=d(x)，即(father,x)不在圈中，則(father, x)就是橋。. 廣度優(yōu)先搜索 Breadth first search (BFS). 拓?fù)渑判?Topological sort拓?fù)渑判蚴菍?duì)有向無圈圖(DAG)頂點(diǎn)的一種排序，它使得如果存在u,v的有向路徑，那么滿足序中u在v前。拓?fù)渑判蚓褪怯梢环N偏序(partical order)得到一個(gè)全序(稱為拓?fù)溆行?topological order))。偏序是滿足自反性，反對(duì)稱性，傳遞性的序。拓補(bǔ)排序的思路很簡(jiǎn)單，就是每次任意找一個(gè)入度為0的點(diǎn)輸出，并把這個(gè)點(diǎn)以及與這個(gè)點(diǎn)相關(guān)的邊刪除。實(shí)際算法中，用一個(gè)隊(duì)列實(shí)現(xiàn)。算法：1. 把所有入度=0的點(diǎn)入隊(duì)Q。2. 若隊(duì)Q非空，則點(diǎn)u出隊(duì)，輸出u；否則轉(zhuǎn)4。3. 把所有與點(diǎn)u相關(guān)的邊(u,v)刪除，若此過程中有點(diǎn)v的入度變?yōu)?，則把v入隊(duì)Q，轉(zhuǎn)2。4. 若出隊(duì)點(diǎn)數(shù)N，則有圈；否則輸出結(jié)果。算法復(fù)雜度: O(m)。習(xí)題：MIPT 012 Correct dictionary設(shè)R為非空集合A上的二元關(guān)系，如果R滿足自反性(對(duì)于每一個(gè)x∈A，(x,x)∈R )，反對(duì)稱性((x,y)∈R∧(y,x)∈R→x=y )和傳遞性((x,y)∈R∧(y,x)∈R→(x,z)∈R)，則稱R為A上的偏序關(guān)系，記作≤。如果(x,y)∈R，則記作x≤y，讀作“x小于等于y”。存在偏序關(guān)系的集合A稱為偏序集(partical order)。拓?fù)渑判虻挠?jì)數(shù)。？？？？？？？？？？？？？？？？？？？？？？？？？？？？？AOV(activity on vertex network)AOE(activity on edge network)，其中頂點(diǎn)表示事件event，權(quán)表示時(shí)間。. 路徑與回路 Paths and circuits . 歐拉路徑或回路 Eulerian path對(duì)于連通的可重邊的圖G，若存在一回路，它通過G的所有邊一次且僅一次，則這回路稱為歐拉路徑或回路。著名的問題：The K246。nigsberg Bridges下面討論有向性：. 無向圖習(xí)題：Ural 1124 Mosaic. 有向圖習(xí)題：CEOI 2005 Depot Rearrangement. 混合圖混合圖是指有的邊是有向的，有的邊是無向的圖。由于無向邊只能經(jīng)過一次，所以不能拆成兩條方向相反的有向邊，只能給無向邊定向，使得定向后的圖滿足“入度等于出度”。見LRJ P324。下面討論在有權(quán)性上的擴(kuò)展：. 無權(quán)圖 Unweighted. 有權(quán)圖 Weighed — 中國郵路問題The Chinese post problem這就是一個(gè)經(jīng)典的問題中國郵路問題：給出一個(gè)連通的無向的可重邊的有權(quán)圖G，求最短的回路，使得每邊至少遍歷1次。由于每邊至少遍歷一次，所以最短路的瓶頸就在于重復(fù)遍歷。由于圖一直保持連通性，所以兩兩奇點(diǎn)之間都存在歐拉路；又兩兩奇點(diǎn)之間的最短路可求；奇點(diǎn)個(gè)數(shù)為偶數(shù)。所以問題就等價(jià)于找一個(gè)奇點(diǎn)構(gòu)成的完全圖G’(V,E)的最小權(quán)匹配(Perfect Matching in General Graph)。V(G’)為原圖G中的奇點(diǎn)，每條邊為兩奇點(diǎn)對(duì)應(yīng)原圖的最短路長度。算法：1. 確定G中的奇點(diǎn)，構(gòu)成G’。2. 確定G’兩兩結(jié)點(diǎn)在G中的最短路作為它們?cè)贕’中的邊權(quán)。3. 對(duì)G’進(jìn)行最小權(quán)匹配。4. 最小權(quán)匹配里的各匹配邊所對(duì)應(yīng)的路徑在G中被重復(fù)遍歷一次,得到歐拉圖G’’。5. 對(duì)G’’找一條歐拉路即可。有向的中國郵路問題，比較復(fù)雜。. Hamiltonian Cycle 哈氏路徑與回路分支限界搜索模擬退火. 無權(quán)圖 Unweighted. 有權(quán)圖 Weighed — 旅行商問題The travelling salesman problem動(dòng)態(tài)規(guī)劃. 網(wǎng)絡(luò)優(yōu)化 Network optimization. 最小生成樹 Minimum spanning trees最小生成樹是指連通圖中所有生成樹中邊權(quán)和最小的一個(gè)。即：求G的一棵生成樹T，使得. 基本算法 Basic algorithms. Prim基本思想：不斷擴(kuò)展一棵子樹，直到包括原圖的全部頂點(diǎn)，得到最小生成樹T。每次增加一條邊，使得這條邊是由當(dāng)前子樹結(jié)點(diǎn)集及其補(bǔ)集所形成的邊割集的最小邊。令d(v)為v到結(jié)點(diǎn)集S的最小距離。算法：1. ,d()=0 (這里是任意一個(gè)結(jié)點(diǎn)),2. 若，則結(jié)束；否則，轉(zhuǎn)3。3. 找補(bǔ)集中的d最小的節(jié)點(diǎn)，加入。更新與相鄰的結(jié)點(diǎn)的d值，即若，則，轉(zhuǎn)2。這里的d可以用優(yōu)先隊(duì)列實(shí)現(xiàn)，需用到刪除最小(DeleteMin)與減值(DecreaseKey)的操作。假設(shè)用Fibonacci Heap實(shí)現(xiàn)(刪除最小O(logn)，減值O(1))，算法復(fù)雜度：。. Kruskal基本思想：就是維護(hù)一個(gè)生成森林。每次將一條權(quán)最小的邊加入子圖T中，并保證不形成圈。如果當(dāng)前弧加入后不形成圈，則加入這條弧，如果當(dāng)前弧加入后會(huì)形成圈，則不加入這條弧，并考慮下一條弧。算法：1. ，將E中的邊按權(quán)從小到大排序。2. i=i+1，若im，結(jié)束，此時(shí)G沒有生成樹；否則判斷是否含圈，是則轉(zhuǎn)2，否則轉(zhuǎn)3。3. 。若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹。 分離集合(disjoint set)，可用并查集實(shí)現(xiàn)。由于排序是的。所以復(fù)雜度為。. Sollin（Boruvka）基本思想：前面介紹的兩種算法的綜合。每次迭代同時(shí)擴(kuò)展多棵子樹，直到得到最小生成樹 T。 算法：1. 對(duì)于所有。2. 若|T|=N，結(jié)束，此時(shí)T為G的最小生成樹；否則，對(duì)于T中所有的子樹集合，計(jì)算它的邊割中的最小?。ㄓ械臅Q連接兩個(gè)連通分量的最小弧“安全邊”）。3. 對(duì)T中所有子樹集合及其邊割最小弧，將與q所在的子樹集合合并。轉(zhuǎn)2。由于每次循環(huán)迭代時(shí)，每棵樹都會(huì)合并成一棵較大的子樹，因此每次循環(huán)迭代都會(huì)使子樹的數(shù)量至少減少一半，或者說第i次迭代每個(gè)分量大小至少為。所以，循環(huán)迭代的總次數(shù)為O(logn)。每次循環(huán)迭代所需要的計(jì)算時(shí)間：對(duì)于第2步，每次檢查所有邊O(m)，去更新每個(gè)連通分量的最小??；對(duì)于第3步，合并個(gè)子樹。所以總的復(fù)雜度為。. 擴(kuò)展模型 Extended models. 度限制生成樹 Minimum degreebounded spanning trees由于這個(gè)問題是NPHard的，一般用搜索算法解決。本文就只討論一種特殊多項(xiàng)式情況：?jiǎn)吸c(diǎn)度限制(one node degree bounded)。把度限制的點(diǎn)記為，滿足度限制。一種貪心的思路：在最小生成樹T的基礎(chǔ)上，通過添刪邊來改造樹，使之逐漸滿足度限制條件。算法：1. 求圖的最小生成樹T。2. 若已滿足度限制，結(jié)束；否則轉(zhuǎn)3。3. 對(duì)于刪去后的每一個(gè)連通分支(為一棵樹)，求添加邊割中的最小弧，刪除邊割里的最大弧后的生成樹中的邊權(quán)和最小的一個(gè)。更新最小生成樹T。轉(zhuǎn)2。第3步，的度少1。習(xí)題：NOI 2005 小H的聚會(huì). k小生成樹 The k minimum spanning tree problem(kMST)生成樹T刪除一條邊f(xié)并加入一條新邊e的操作稱為交換。若交換后的圖仍是一顆樹，則此交換稱為可行交換。若生成樹T可通過一次交換成為生成樹T’，則