最大匹配圖演算法
A. 圖像匹配的演算法
迄今為止，人們已經提出了各種各樣的圖像匹配演算法，但從總體上講，這些匹配演算法可以分成關系結構匹配方法、結合特定理論工具的匹配方法、基於灰度信息的匹配方法、基於亞像元匹配方法、基於內容特徵的匹配方法五大類型 基於內容特徵的匹配首先提取反映圖像重要信息的特徵，而後以這些特徵為模型進行匹配。局部特徵有點、邊緣、線條和小的區域，全局特徵包括多邊形和稱為結構的復雜的圖像內容描述。特徵提取的結果是一個含有特徵的表和對圖像的描述，每一個特徵由一組屬性表示，對屬性的進一步描述包括邊緣的定向和弧度，邊與線的長度和曲率，區域的大小等。除了局部特徵的屬性外，還用這些局部特徵之間的關系描述全局特徵，這些關系可以是幾何關系，例如兩個相鄰的三角形之間的邊，或兩個邊之間的距離可以是輻射度量關系，例如灰度值差別，或兩個相鄰區域之間的灰度值方差或拓撲關系，例如一個特徵受限於另一個特徵。人們一般提到的基於特徵的匹配絕大多數都是指基於點、線和邊緣的局部特徵匹配，而具有全局特徵的匹配實質上是我們上面提到的關系結構匹配方法。特徵是圖像內容最抽象的描述，與基於灰度的匹配方法比，特相對於幾何圖像和輻射影響來說更不易變化，但特徵提取方法的計算代價通常較，並且需要一些自由參數和事先按照經驗選取的閉值，因而不便於實時應用同時，在紋理較少的圖像區域提取的特徵的密度通常比較稀少，使局部特徵的提 取比較困難。另外，基於特徵的匹配方法的相似性度量也比較復雜，往往要以特徵屬性、啟發式方法及閉方法的結合來確定度量方法。基於圖像特徵的匹配方法可以克服利用圖像灰度信息進行匹配的缺點，由於圖像的特徵點比象素點要少很多，因而可以大大減少匹配過程的計算量同時，特徵點的匹配度量值對位置的變化比較敏感，可以大大提高匹配的精確程度而且，特徵點的提取過程可以減少雜訊的影響，對灰度變化，圖像形變以及遮擋等都有較好的適應能力。所以基於圖像特徵的匹配在實際中的應用越來越廣-泛。所使用的特徵基元有點特徵明顯點、角點、邊緣點等、邊緣線段等。
B. 求一般圖的最大權匹配的演算法（最好詳細一些，注意數最大權匹配），高分求助！
Algorithmus 3.3 Kruskal's Algorithm 時間復雜度 O(mlog n)
m邊數 n點數
輸入: 圖 G = (V;E) 和 權c : E -》R.
輸出: 一棵最優樹 T.
begin
把所有邊以權的大小按從小到大排序
T := (VG，ET ) := (VG， 空);
for i = 1 to m do
if T + ei 沒有圈 then
T := (VG;ET 並上 {ei});
if end
for end
end
或者 Algorithmus 3.5 Prim's Algorithm 時間復雜度O(m+n log n)
C. 衡量演算法效率的方法與准則
演算法效率與分析
數據結構作為程序設計的基礎，其對演算法效率的影響必然是不可忽視的。本文就如何合理選擇數據結構來優化演算法這一問題，對選擇數據結構的原則和方法進行了一些探討。首先對數據邏輯結構的重要性進行了分析，提出了選擇邏輯結構的兩個基本原則；接著又比較了順序和鏈式兩種存儲結構的優點和缺點，並討論了選擇數據存儲結構的方法；最後本文從選擇數據結構的的另一角度出發，進一步探討了如何將多種數據結構進行結合的方法。在討論方法的同時，本文還結合實際，選用了一些較具有代表性的信息學競賽試題舉例進行了分析
【正文】一、引論
「數據結構＋演算法＝程序」，這就說明程序設計的實質就是對確定的問題選擇一種合適的數據結構，加上設計一種好的演算法。由此可見，數據結構在程序設計中有著十分重要的地位。
數據結構是相互之間存在一種或多種特定關系的數據元素的集合。因為這其中的「關系」，指的是數據元素之間的邏輯關系，因此數據結構又稱為數據的邏輯結構。而相對於邏輯結構這個比較抽象的概念，我們將數據結構在計算機中的表示又稱為數據的存儲結構。
建立問題的數學模型，進而設計問題的演算法，直至編出程序並進行調試通過，這就是我們解決信息學問題的一般步驟。我們要建立問題的數學模型，必須首先找出問題中各對象之間的關系，也就是確定所使用的邏輯結構；同時，設計演算法和程序實現的過程，必須確定如何實現對各個對象的操作，而操作的方法是決定於數據所採用的存儲結構的。因此，數據邏輯結構和存儲結構的好壞，將直接影響到程序的效率。
二、選擇合理的邏輯結構
在程序設計中，邏輯結構的選用就是要分析題目中的數據元素之間的關系，並根據這些特定關系來選用合適的邏輯結構以實現對問題的數學描述，進一步解決問題。邏輯結構實際上是用數學的方法來描述問題中所涉及的操作對象及對象之間的關系，將操作對象抽象為數學元素，將對象之間的復雜關系用數學語言描述出來。
根據數據元素之間關系的不同特性，通常有以下四種基本邏輯結構：集合、線性結構、樹形結構、圖狀（網狀）結構。這四種結構中，除了集合中的數據元素之間只有「同屬於一個集合」的關系外，其它三種結構數據元素之間分別為「一對一」、「一對多」、「多對多」的關系。
因此，在選擇邏輯結構之前，我們應首先把題目中的操作對象和對象之間的關系分析清楚，然後再根據這些關系的特點來合理的選用邏輯結構。尤其是在某些復雜的問題中，數據之間的關系相當復雜，且選用不同邏輯結構都可以解決這一問題，但選用不同邏輯結構實現的演算法效率大不一樣。
對於這一類問題，我們應採用怎樣的標准對邏輯結構進行選擇呢？
下文將探討選擇合理邏輯結構應充分考慮的兩個因素。
一、 充分利用「可直接使用」的信息。
首先，我們這里所講的「信息」，指的是元素與元素之間的關系。
對於待處理的信息，大致可分為「可直接使用」和「不可直接使用」兩類。對於「可直接使用」的信息，我們使用時十分方便，只需直接拿來就可以了。而對於「不可直接使用」的這一類，我們也可以通過某些間接的方式，使之成為可以使用的信息，但其中轉化的過程顯然是比較浪費時間的。
由此可見，我們所需要的是盡量多的「可直接使用」的信息。這樣的信息越多，演算法的效率就會越高。
對於不同的邏輯結構，其包含的信息是不同的，演算法對信息的利用也會出現不同的復雜程度。因此，要使演算法能夠充分利用「可直接使用」的信息，而避免演算法在信息由「不可直接使用」向「可直接使用」的轉化過程中浪費過多的時間，我們必然需要採用一種合理的邏輯結構，使其包含更多「可直接使用」的信息。
〖問題一〗 IOI99的《隱藏的碼字》。
〖問題描述〗
問題中給出了一些碼字和一個文本，要求編程找出文本中包含這些碼字的所有項目，並將找出的項目組成一個最優的「答案」，使得答案中各項目所包含的碼字長度總和最大。每一個項目包括一個碼字，以及該碼字在文本中的一個覆蓋序列（如』abcadc』就是碼字』abac』的一個覆蓋序列），並且覆蓋序列的長度不超過1000。同時，「答案」要求其中每個項目的覆蓋序列互相沒有重疊。
〖問題分析〗
對於此題，一種較容易得出的基本演算法是：對覆蓋序列在文本中的終止位置進行循環，再判斷包含了哪些碼字，找出所有項目，並最後使用動態規劃的方法將項目組成最優的「答案」。
演算法的其它方面我們暫且不做考慮，而先對問題所採用的邏輯結構進行選擇。
如果我們採用線性的邏輯結構（如循環隊列），那麼我們在判斷是否包含某個碼字t時，所用的方法為：初始時用指針p指向終止位置，接著通過p的不斷前移，依次找出碼字t從尾到頭的各個字母。例如碼字為「ABDCAB」，而文本圖1-1，終止位置為最右邊的箭頭符號，每個箭頭代表依次找到的碼字的各個字母。
指針p的移動方向
A B D C A B
C D A C B D C A D C D B A D C C B A D
圖1-1
由於題目規定碼字的覆蓋序列長度不超過1000，所以進行這樣的一次是否包含的判斷，其復雜度為O(1000)。
由於碼字t中相鄰兩字母在文本中的位置，並非只有相鄰(如圖1-1中的』D』和』C』)這一種關系，中間還可能間隔了許多的字母(如圖1-1中』C』和』A』就間隔了2個字母)，而線性結構中擁有的信息，僅僅只存在於相鄰的兩元素之間。通過這樣簡單的信息來尋找碼字的某一個字母，其效率顯然不高。
如果我們建立一個有向圖，其中頂點i(即文本的第i位)用52條弧分別連接』a』..』z』,』A』..』Z』這52個字母在i位以前最後出現的位置（如圖1-2的連接方式），我們要尋找碼字中某個字母的前一個字母，就可以直接利用已連接的邊，而不需用枚舉的方法。我們也可以把問題看為：從有向圖的一個頂點出發，尋找一條長度為length(t)-1的路徑，並且路徑中經過的頂點，按照碼字t中的字母有序。
C D A C B D C A D C D B A D C C B A D
圖1-2
通過計算，用圖進行記錄在空間上完全可以承受(記錄1000個點×52條弧×4位元組的長整型=200k左右)。在時間上，由於可以充分利用第i位和第i+1位弧的連接方式變化不大這一點(如圖1-2所示，第i位和第i+1位只有一條弧的指向發生了變化，即第i+1位將其中一條弧指向了第i位)，所以要對圖中的弧進行記錄，只需對弧的指向進行整體賦值，並改變其中的某一條弧即可。
因此，我們通過採用圖的邏輯結構，使得尋找字母的效率大大提高，其判斷的復雜度為O(length(t))，最壞為O(100)，比原來方法的判斷效率提高了10倍。
（附程序codes.pas）
對於這個例子，雖然用線性的數據結構也可以解決，但由於判斷的特殊性，每次需要的信息並不能從相鄰的元素中找到，而線性結構中只有相鄰元素之間存在關系的這一點，就成為了一個很明顯的缺點。因此，問題一線性結構中的信息，就屬於「不可直接使用」的信息。相對而言，圖的結構就正好滿足了我們的需要，將所有可能產生關系的點都用弧連接起來，使我們可以利用弧的關系，高效地進行判斷尋找的過程。雖然圖的結構更加復雜，但卻將「不可直接使用」的信息，轉化成為了「可直接使用」的信息，演算法效率的提高，自然在情理之中。。
二、 不記錄「無用」信息。
從問題一中我們看到，由於圖結構的信息量大，所以其中的信息基本上都是「可用」的。但是，這並不表示我們就一定要使用圖的結構。在某些情況下，圖結構中的「可用」信息，是有些多餘的。
信息都「可用」自然是好事，但倘若其中「無用」（不需要）的信息太多，就只會增加我們思考分析和處理問題時的復雜程度，反而不利於我們解決問題了。
〖問題二〗 湖南省1997年組隊賽的《乘船問題》
〖問題描述〗
有N個人需要乘船，而每船最多隻能載兩人，且必須同名或同姓。求最少需要多少條船。
〖問題分析〗
看到這道題，很多人都會想到圖的數據結構：將N個人看作無向圖的N個點，凡同名或同姓的人之間都連上邊。
要滿足用船最少的條件，就是需要盡量多的兩人共乘一條船，表現在圖中就是要用最少的邊完成對所有頂點的覆蓋。這就正好對應了圖論的典型問題：求最小邊的覆蓋。所用的演算法為「求任意圖最大匹配」的演算法。
使用「求任意圖最大匹配」的演算法比較復雜(要用到擴展交錯樹，對花的收縮等等)，效率也不是很高。因此，我們必須尋找一個更簡單高效的方法。
首先，由於圖中任兩個連通分量都是相對獨立的，也就是說任一條匹配邊的兩頂點，都只屬於同一個連通分量。因此，我們可以對每個連通分量分別進行處理，而不會影響最終的結果。
同時，我們還可以對需要船隻s的下限進行估計：
對於一個包含Pi個頂點的連通分量，其最小覆蓋邊數顯然為[Pi/2]。若圖中共有L個連通分量，則s=∑[Pi/2](1<=i<=L)。
然後，我們通過多次嘗試，可得出一個猜想：
實際需要的覆蓋邊數完全等於我們求出的下限∑[Pi/2](1<=i<=L)。
要用圖的結構對上述猜想進行證明，可參照以下兩步進行：
1． 連通分量中若不存在度為1的點，就必然存在迴路。
2． 從圖中刪去度為1的點及其相鄰的點，或刪去迴路中的任何一邊，連通分量依然連通，即連通分量必然存在非橋邊。
由於圖的方法不是這里的重點，所以具體證明不做詳述。而由採用圖的數據結構得出的演算法為：每次輸出一條非橋的邊，並從圖中將邊的兩頂點刪去。此演算法的時間復雜度為O(n3)。（尋找一條非橋邊的復雜度為O(n2)，尋找覆蓋邊操作的復雜度為O(n)）
由於受到圖結構的限制，時間復雜度已經無法降低，所以如果我們要繼續對演算法進行優化，只有考慮使用另一種邏輯結構。這里，我想到了使用二叉樹的結構，具體說就是將圖中的連通分量都轉化為二叉樹，用二叉樹來解決問題。
首先，我們以連通分量中任一個頂點作為樹根，然後我們來確定建樹的方法。
1． 找出與根結點i同姓的點j（j不在二叉樹中）作為i的左兒子，再以j為樹根建立子樹。
2． 找出與根結點i同名的點k（k不在二叉樹中）作為i的右兒子，再以k為樹根建立子樹。
如圖2-1-1中的連通分量，我們通過上面的建樹方法，可以使其成為圖2-1-2中的二叉樹的結構(以結點1為根)。（兩點間用實線表示同姓，虛線表示同名）
圖2-1-2
圖2-1-1
接著，我就來證明這棵樹一定包含了連通分量中的所有頂點。
【引理2.1】
若二叉樹T中包含了某個結點p，那麼連通分量中所有與p同姓的點一定都在T中。
證明：
為了論證的方便，我們約定：s表示與p同姓的頂點集合；lc[p,0]表示結點p，lc[p,i](i>0)表示lc[p,i-1]的左兒子，顯然lc[p,i]與p是同姓的。
假設存在某個點q，滿足qs且qT。由於s是有限集合，因而必然存在某個lc[p,k]無左兒子。則我們可以令lc[p,k+1]=q，所以qT，與假設qT相矛盾。
所以假設不成立，原命題得證。
由引理2.1的證明方法，我們同理可證引理2.2。
【引理2.2】
若二叉樹T中包含了某個結點p，那麼連通分量中所有與p同名的點一定都在T中。
有了上面的兩個引理，我們就不難得出下面的定理了。
【定理一】
以連通分量中的任一點p作為根結點的二叉樹，必然能夠包含連通分量中的所有頂點。
證明：
由引理2.1和引理2.2，所有與p同姓或同名的點都一定在二叉樹中，即連通分量中所有與p有邊相連的點都在二叉樹中。由連通分量中任兩點間都存在路徑的特性，該連通分量中的所有點都在二叉樹中。
在證明二叉樹中包含了連通分量的所有頂點後，我們接著就需要證明我們的猜想，也就是下面的定理：
【定理二】包含m個結點的二叉樹Tm，只需要船的數量為boat[m]=[m/2](mN)。
證明：
(i) 當m=1,m=2,m=3時命題顯然成立。
圖2-2-1
圖2-2-2
圖2-2-3
(ii) 假設當m<k(k>3)時命題成立，那麼當m=k時，我們首先從樹中找到一個層次最深的結點，並假設這個結點的父親為p。那麼，此時有且只有以下三種情況（結點中帶有陰影的是p結點）：
(1) 如圖2-2-1，p只有一個兒子。此時刪去p和p唯一的兒子，Tk就成為了Tk-2，則boat[k]=boat[k-2]+1=[(k-2)/2]+1=[k/2]。
(2) 如圖2-2-2，p有兩個兒子，並且p是其父親的左兒子。此時可刪去p和p的右兒子，並可將p的左兒子放到p的位置上。同樣地，Tk成為了Tk-2，boat[k]=boat[k-2]+1=[k/2]。
(3) 如圖2-2-3，p有兩個兒子，並且p是其父親的右兒子。此時可刪去p和p的左兒子，並可將p的右兒子放到p的位置上。情況與(2)十分相似，易得此時得boat[k]=boat[k-2]+1=[k/2]。
綜合(1)、(2)、(3)，當m=k時，boat[k]=[k/2]。
最後，綜合(i)、(ii)，對於一切mN，boat[m]=[m/2]。
由上述證明，我們將問題中數據的圖結構轉化為樹結構後，可以得出求一棵二叉樹的乘船方案的演算法：
proc try(father:integer;var root:integer;var rest:byte);
{輸出root為樹根的子樹的乘船方案，father=0表示root是其父親的左兒子，
father=1表示root是其父親的右兒子，rest表示輸出子樹的乘船方案後，
是否還剩下一個根結點未乘船}
begin
visit[root]:=true; {標記root已訪問}
找到一個與root同姓且未訪問的結點j;
if j<>n+1 then try(0,j,lrest);
找到一個與root同姓且未訪問的結點k;
if k<>n+1 then try(1,k,rrest);
if (lrest=1) xor (rrest=1) then begin {判斷root是否只有一個兒子，情況一}
if lrest=1 then print(lrest,root) else print(rrest,root);
rest:=0;
end
else if (lrest=1) and (rrest=1) then begin {判斷root是否有兩個兒子}
if father=0 then begin
print(rrest,root);root:=j; {情況二}
end
else begin
print(lrest,root);root:=k; {情況三}
end;
rest:=1;
end
else rest:=1;
end;
這只是輸出一棵二叉樹的乘船方案的演算法，要輸出所有人的乘船方案，我們還需再加一層循環，用於尋找各棵二叉樹的根結點，但由於每個點都只會訪問一次，尋找其左右兒子各需進行一次循環，所以演算法的時間復雜度為O(n2)。（附程序boat.pas）
最後，我們對兩種結構得出不同時間復雜度演算法的原因進行分析。其中最關鍵的一點就是因為二叉樹雖然結構相對較簡單，但已經包含了幾乎全部都「有用」的信息。由我們尋找乘船方案的演算法可知，二叉樹中的所有邊不僅都發揮了作用，而且沒有重復的使用，可見信息的利用率也是相當之高的。
既然採用樹結構已經足夠，圖結構中的一些信息就顯然就成為了「無用」的信息。這些多餘的「無用」信息，使我們在分析問題時難於發現規律，也很難找到高效的演算法進行解決。這正如迷宮中的牆一樣，越多越難走。「無用」的信息，只會干擾問題的規律性，使我們更難找出解決問題的方法。
小結
我們對數據的邏輯結構進行選擇，是構造數學模型一大關鍵，而演算法又是用來解決數學模型的。要使演算法效率高，首先必須選好數據的邏輯結構。上面已經提出了選擇邏輯結構的兩個條件（思考方向），總之目的是提高信息的利用效果。利用「可直接使用」的信息，由於中間不需其它操作，利用的效率自然很高；不不記錄「無用」的信息，就會使我們更加專心地研究分析「有用」的信息，對信息的使用也必然會更加優化。
總之，在解決問題的過程中，選擇合理的邏輯結構是相當重要的環
三、 選擇合理的存儲結構
數據的存儲結構，分為順序存儲結構和鏈式存儲結構。順序存儲結構的特點是藉助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系；鏈式存儲結構則是藉助指示元素存儲地址的指針表示數據元素之間的邏輯關系。
因為兩種存儲結構的不同，導致這兩種存儲結構在具體使用時也分別存在著優點和缺點。
這里有一個較簡單的例子：我們需要記錄一個n×n的矩陣，矩陣中包含的非0元素為m個。
此時，我們若採用順序存儲結構，就會使用一個n×n的二維數組，將所有數據元素全部記錄下來；若採用鏈式存儲結構，則需要使用一個包含m個結點的鏈表，記錄所有非0的m個數據元素。由這樣兩種不同的記錄方式，我們可以通過對數據的不同操作來分析它們的優點和缺點。
1． 隨機訪問矩陣中任意元素。由於順序結構在物理位置上是相鄰的，所以可以很容易地獲得任意元素的存儲地址，其復雜度為O(1)；對於鏈式結構，由於不具備物理位置相鄰的特點，所以首先必須對整個鏈表進行一次遍歷，尋找需進行訪問的元素的存儲地址，其復雜度為O(m)。此時使用順序結構顯然效率更高。
2． 對所有數據進行遍歷。兩種存儲結構對於這種操作的復雜度是顯而易見的，順序結構的復雜度為O(n2)，鏈式結構為O(m)。由於在一般情況下m要遠小於n2，所以此時鏈式結構的效率要高上許多。
除上述兩種操作外，對於其它的操作，這兩種結構都不存在很明顯的優點和缺點，如對鏈表進行刪除或插入操作，在順序結構中可表示為改變相應位置的數據元素。
既然兩種存儲結構對於不同的操作，其效率存在較大的差異，那麼我們在確定存儲結構時，必須仔細分析演算法中操作的需要，合理地選擇一種能夠「揚長避短」的存儲結構。
一、合理採用順序存儲結構。
我們在平常做題時，大多都是使用順序存儲結構對數據進行存儲。究其原因，一方面是出於順序結構操作方便的考慮，另一方面是在程序實現的過程中，使用順序結構相對於鏈式結構更便於對程序進行調試和查找錯誤。因此，大多數人習慣上認為，能夠使用順序結構進行存儲的問題，最「好」採用順序存儲結構。
其實，這個所謂的「好」只是一個相對的標准，是建立在以下兩個前提條件之下的：
1． 鏈式結構存儲的結點與順序結構存儲的結點數目相差不大。這種情況下，由於存儲的結點數目比較接近，使用鏈式結構完全不能體現出記錄結點少的優點，並且可能會由於指針操作較慢而降低演算法的效率。更有甚者，由於指針自身佔用的空間較大，且結點數目較多，因而演算法對空間的要求可能根本無法得到滿足。
2． 並非演算法效率的瓶頸所在。由於不是演算法最費時間的地方，這里是否進行改進，顯然是不會對整個演算法構成太大影響的，若使用鏈式結構反而會顯得操作過於繁瑣。
二、必要時採用鏈式存儲結構。
上面我對使用順序存儲結構的條件進行了分析，最後就只剩下何時應該採用鏈式存儲結構的問題了。
由於鏈式結構中指針操作確實較繁瑣，並且速度也較慢，調試也不方便，因而大家一般都不太願意用鏈式的存儲結構。但是，這只是一般的觀點，當鏈式結構確實對演算法有很大改進時，我們還是不得不進行考慮的。
〖問題三〗 IOI99的《地下城市》。
〖問題描述〗
已知一個城市的地圖，但未給出你的初始位置。你需要通過一系列的移動和探索，以確定初始時所在的位置。題目的限制是：
1． 不能移動到有牆的方格。
2． 只能探索當前所在位置四個方向上的相鄰方格。
在這兩個限制條件下，要求我們的探索次數（不包括移動）盡可能的少。
〖問題分析〗
由於存儲結構要由演算法的需要確定，因此我們首先來確定問題的演算法。
經過對問題的分析，我們得出解題的基本思想：先假設所有無牆的方格都可能是初始位置，再通過探索一步步地縮小初始位置的范圍，最終得到真正的初始位置。同時，為提高演算法效率，我們還用到了分治的思想，使我們每一次探索都盡量多的縮小初始位置的范圍(使程序盡量減少對運氣的依賴)。
接著，我們來確定此題的存儲結構。
由於這道題的地圖是一個二維的矩陣，所以一般來講，採用順序存儲結構理所當然。但是，順序存儲結構在這道題中暴露了很大的缺點。我們所進行的最多的操作，一是對初始位置的范圍進行篩選，二是判斷要選擇哪個位置進行探索。而這兩種操作，所需要用到的數據，只是龐大地圖中很少的一部分。如果採用順序存儲結構(如圖3-1中陰影部分表示已標記)，無論你需要用到多少數據，始終都要完全的遍歷整個地圖。
4
3
2
1
1 2 3 4
圖3-1
head
圖3-2
然而，如果我們採用的是鏈式存儲結構(如圖3-2的鏈表)，那麼我們需要多少數據，就只會遍歷多少數據，這樣不僅充分發揮了鏈式存儲結構的優點，而且由於不需單獨對某一個數據進行提取，每次都是對所有數據進行判斷，從而避免了鏈式結構的最大缺點。
我們使用鏈式存儲結構，雖然沒有降低問題的時間復雜度(鏈式存儲結構在最壞情況下的存儲量與順序存儲結構的存儲量幾乎相同)，但由於體現了前文所述選擇存儲結構時揚長避短的原則，因而演算法的效率也大為提高。（程序對不同數據的運行時間見表3-3）
測試數據編號 使用順序存儲結構的程序 使用鏈式存儲結構的程序
1 0.06s 0.02s
2 1.73s 0.07s
3 1.14s 0.06s
4 3.86s 0.14s
5 32.84s 0.21s
6 141.16s 0.23s
7 0.91s 0.12s
8 6.92s 0.29s
9 6.10s 0.23s
10 17.41s 0.20s
表3-3
（附使用鏈式存儲結構的程序under.pas）
我們選擇鏈式的存儲結構，雖然操作上可能稍復雜一些，但由於改進了演算法的瓶頸，演算法的效率自然也今非昔比。由此可見，必要時選擇鏈式結構這一方法，其效果是不容忽視的。
小結
合理選擇邏輯結構，由於牽涉建立數學模型的問題，可能大家都會比較注意。但是對存儲結構的選擇，由於不會對演算法復雜度構成影響，所以比較容易忽視。那麼，這種不能降低演算法復雜度的方法是否需要重視呢？
大家都知道，剪枝作為一種常用的優化演算法的方法，被廣泛地使用，但剪枝同樣是無法改變演算法的復雜度的。因此，作用與剪枝相似的存儲結構的合理選擇，也是同樣很值得重視的。
總之，我們在設計演算法的過程中，必須充分考慮存儲結構所帶來的不同影響，選擇最合理的存儲結構。
四、 多種數據結構相結合
上文所探討的，都是如何對數據結構進行選擇，其中包含了邏輯結構的選擇和存儲結構的選擇，是一種具有較大普遍性的演算法優化方法。對於多數的問題，我們都可以通過選擇一種合理的邏輯結構和存儲結構以達到優化演算法的目的。
但是，有些問題卻往往不如人願，要對這類問題的數據結構進行選擇，常常會顧此失彼，有時甚至根本就不存在某一種合適的數據結構。此時，我們是無法選擇出某一種合適的數據結構的，以上的方法就有些不太適用了。
為解決數據結構難以選擇的問題，我們可以採用將多種數據結構進行結合的方法。通過多種數據結構相結合，達到取長補短的作用，使不同的數據結構在演算法中發揮出各自的優勢。
這只是我們將多種數據結構進行結合的總思想，具體如何進行結合，我們可以先看下面的例子。
我們可以採用映射的方法，將線性結構中的元素與堆中間的結點一一對應起來，若線性的數組中的元素發生變化，堆中相應的結點也接著變化，堆中的結點發生變化，數組中相應的元素也跟著變化。
將兩種結構進行結合後，無論是第一步還是第二步，我們都不需對所有元素進行遍歷，只需進行常數次復雜度為O(log2n)的堆化操作。這樣，整個時間復雜度就成為了O(nlog2n)，演算法效率無疑得到了很大提高。
五、 總結
我們平常使用數據結構，往往只將其作為建立模型和演算法實現的工具，而沒有考慮這種工具對程序效率所產生的影響。信息學問題隨著難度的不斷增大，對演算法時空效率的要求也越來越高，而演算法的時空效率，在很大程度上都受到了數據結構的制約。
D. 二分圖最大匹配Matlab程序（在線等，感激不盡！）
第一個問題比較簡單，這里懶得對著你的圖片敲數據，用隨機數代替
long=100;
A=0.1*rand(long,1);
B=0.15*rand(long,1);
[AA BB]=meshgrid(A,B);
gg=0.5017*AA-0.65*BB;
g=gg>=-0.03&gg<=0.03; %這就是gij矩陣，相當於二分圖的連接矩陣
[num h] = maxnum(g);%第二個問題就是求二分圖的最大匹配問題，這里
%調用了一個自己寫maxnum函數，返回num就是最大值，h是hij(不唯一）
以下是maxnum.m的內容，用的是匈牙利演算法
其中還用了一個遞歸的incpath函數，尋找增廣路徑
function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩陣hij記錄選中
globalG_g;%矩陣gij記錄匹配
globalG_v;%記錄當前一次路徑訪問過的節點
G_h=false(s);%矩陣hij初始為空
G_g=g;%矩陣gij就是傳遞進來的參數g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化徑訪問過的節點為空
incpath(i);%從Ai開始尋找增廣路徑
end
h=G_h;num=sum(h(:));%輸出最大匹配數，和匹配矩陣h
clearglobal'G_h';clearglobal'G_g';
end
functionOK=incpath(i)%從Ai開始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%尋找合條件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，標記Bj為以訪問節點
ii=find(G_h(:,j));%尋找Bj在原來匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增廣路徑末端，返回true
ok=incpath(ii);%如果在原來的匹配中，根據匹配對應的Aii遞歸調用incpath尋找
ifok%如果遞歸尋找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路徑反色返回true
end
E. 二分圖最大匹配的Hopcroft-Carp演算法的pascal實現，求各神牛，懸賞！！！！
program hopcroft_karp;
const maxn=100;
var linkx, linky, distx, disty, queue: array[1..maxn] of longint; //link表示已經匹配的邊 x為左 y為右
map: array[1..maxn, 1..maxn] of boolean;
n, m, i, x, y, ans: longint;
function bfs: boolean;
var i, now, head, tail: longint;
begin
fillchar(distx,sizeof(distx),0); //dist表示該點在增廣路中被搜到時的距離
fillchar(disty,sizeof(disty),0);
bfs:=false;
head:=0; tail:=0;
for i:=1 to n do if (linkx[i]=0) then begin
inc(tail);
queue[tail]:=i;
end;
while (head<tail) do begin //利用隊列搜索增廣路
inc(head); now:=queue[head];
for i:=1 to n do if map[now,i] and (disty[i]=0) then begin //disty[i]<>0: 增廣路不能交叉
disty[i]:=distx[now]+1;
if (linky[i]=0) then bfs:=true
else begin //左邊的點無須判斷dist是否為0
distx[linky[i]]:=disty[i]+1;
inc(tail);
queue[tail]:=linky[i]; //queue只記錄左邊的點
end;
end;
end;
end;
function dfs(x:longint): boolean;
var i: longint;
begin
for i:=1 to n do if map[x,i] and (disty[i]=distx[x]+1) then begin //為了判斷是否能形成增廣路
disty[i]:=0; //dist改為0 防止下次再搜到此點 由於這個條件可能導致增廣路轉道
if (linky[i]=0) or dfs(linky[i]) then begin //有時候會使原來搜索到的一些增廣路無法繼續更新
linkx[x]:=i; //但是不會出現錯誤
linky[i]:=x; //DFS過程類似hungry演算法
exit(true);
end;
end;
exit(false);
end;
begin
fillchar(map,sizeof(map),false);
read(n,m);
for i:=1 to m do begin
read(x,y);
map[x,y]:=true; //map不能賦雙向值
end;
fillchar(linkx,sizeof(linkx),0);
fillchar(linky,sizeof(linky),0);
ans:=0;
while bfs do
for i:=1 to n do
if (linkx[i]=0) and dfs(i) then inc(ans);
writeln(ans);
end.
思路：首先用bfs判斷圖中是否有增廣路，如果有，則利用dist記錄下來，然後用dfs處理增廣路，不斷循環直到不存在增廣路
由於bfs一次可以判斷出許多增廣路，演算法會比hungry快很多，hungry的復雜度為n*m，而hopcroft的復雜度為n^0.5*m
F. 匈牙利法中直線覆蓋選擇的最小值
匈牙利法中直線覆蓋選擇的最小值：二分圖最大匹配數=最小點覆蓋率。
二分圖的最小點覆蓋的理解：找到最少的一些點，使二分圖所有的邊都至少有一個端點在這些點之中。倒過來說就是，刪除包含這些點的邊，可以刪掉所有邊。
最小點覆蓋數：選取最少的點，使任意一條邊至少有一個端點被選擇。最大獨立數：選取最多的點，使任意所選兩點均不相連。
最小路徑覆蓋數：對於一個 DAG（有向無環圖），選取最少條路徑，使得每個頂點屬於且僅屬於一條路徑。路徑長可以為 0（即單個點）。
匈牙利演算法
匈牙利演算法（Hungarian algorithm），其核心就是尋找增廣路徑，是一種用增廣路徑求二分圖最大匹配的演算法。匈牙利演算法是一種在P問題內（多項式時間內）求解任務分配問題的組合優化演算法。它推動了後來的原始對偶方法。
匈牙利演算法是美國數學家哈羅德·庫恩於1955年提出的。此演算法之所以被稱作匈牙利演算法，是因為演算法很大一部分是基於以前匈牙利數學家Dénes Kőnig和Jenő Egerváry的工作之上創建起來的。
G. 什麼是二分圖的匹配,最大匹配,帶權最大匹配
給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附於同一個頂點，則稱M是一個匹配。
選擇這樣的邊數最大的子集稱為圖的最大匹配問題(maximal matching problem)
如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配。
求二分圖最大匹配可以用最大流或者匈牙利演算法。
H. 求二分圖最大匹配的Matlab程序
[numh]=maxnum(g);%g是二分圖鄰接矩陣
%調用了一個自己寫maxnum函數，返回num就是最大值，h是hij(不唯一）
以下是maxnum.m的內容，用的是匈牙利演算法
其中還用了一個遞歸的incpath函數，尋找增廣路徑
function[numh]=maxnum(g)
s=size(g);
globalG_h;%矩陣hij記錄選中
globalG_g;%矩陣gij記錄匹配
globalG_v;%記錄當前一次路徑訪問過的節點
G_h=false(s);%矩陣hij初始為空
G_g=g;%矩陣gij就是傳遞進來的參數g
fori=1:s(1)
G_v=false(1,s(2));%每次初始化徑訪問過的節點為空
incpath(i);%從Ai開始尋找增廣路徑
end
h=G_h;num=sum(h(:));%輸出最大匹配數，和匹配矩陣h
clearglobal'G_h';clearglobal'G_g';
end
functionOK=incpath(i)%從Ai開始
globalG_h;globalG_g;globalG_v;OK=false;
j=find(~G_h(i,:)&G_g(i,:)&~G_v,1);%尋找合條件的Bj
ifisempty(j),return;end%找不到返回false
G_v(j)=true;%找到了，標記Bj為以訪問節點
ii=find(G_h(:,j));%尋找Bj在原來匹配中
ifisempty(ii)%如果不在原匹配中
G_h(i,j)=true;OK=true;return;end%找到增廣路徑末端，返回true
ok=incpath(ii);%如果在原來的匹配中，根據匹配對應的Aii遞歸調用incpath尋找
ifok%如果遞歸尋找返回成功
G_h(i,j)=~G_h(i,j);G_h(ii,j)=~G_h(ii,j);OK=true;return;end%路徑反色返回true
end
I. 離散數學的圖論中的二部圖的完全匹配和最大匹配問題怎麼理解
11個互不同構的生成子圖，18個互不同構的子圖
ps:生成子圖按邊數考慮，邊數從0到6，子圖按頂點數考慮
J. 程序員必須掌握哪些演算法
一.基本演算法:
枚舉. (poj1753,poj2965)
貪心(poj1328,poj2109,poj2586)
遞歸和分治法.
遞推.
構造法.(poj3295)
模擬法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.圖演算法:
圖的深度優先遍歷和廣度優先遍歷.
最短路徑演算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成樹演算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓撲排序 (poj1094)
二分圖的最大匹配 (匈牙利演算法) (poj3041,poj3020)
最大流的增廣路演算法(KM演算法). (poj1459,poj3436)
三.數據結構.
串 (poj1035,poj3080,poj1936)
排序(快排、歸並排(與逆序數有關)、堆排) (poj2388,poj2299)
簡單並查集的應用.
哈希表和二分查找等高效查找法(數的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼樹(poj3253)
堆
trie樹(靜態建樹、動態建樹) (poj2513)
四.簡單搜索
深度優先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
廣度優先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
簡單搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.動態規劃
背包問題. (poj1837,poj1276)
型如下表的簡單DP(可參考lrj的書 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最長公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最優二分檢索樹問題)
六.數學
組合數學:
1.加法原理和乘法原理.
2.排列組合.
3.遞推關系.
(POJ3252,poj1850,poj1019,poj1942)
數論.
1.素數與整除問題
2.進制位.
3.同餘模運算.
(poj2635, poj3292,poj1845,poj2115)
計算方法.
1.二分法求解單調函數相關知識.(poj3273,poj3258,poj1905,poj3122)
七.計算幾何學.
幾何公式.
叉積和點積的運用(如線段相交的判定,點到線段的距離等). (poj2031,poj1039)
多邊型的簡單演算法(求面積)和相關判定(點在多邊型內,多邊型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)
中級（校賽壓軸及省賽中等難度）:
一.基本演算法:
C++的標准模版庫的應用. (poj3096,poj3007)
較為復雜的模擬題的訓練(poj3393,poj1472,poj3371,poj1027,poj2706)
二.圖演算法:
差分約束系統的建立和求解. (poj1201,poj2983)
最小費用最大流(poj2516,poj2516,poj2195)
雙連通分量(poj2942)
強連通分支及其縮點.(poj2186)
圖的割邊和割點(poj3352)
最小割模型、網路流規約(poj3308)
三.數據結構.
線段樹. (poj2528,poj2828,poj2777,poj2886,poj2750)
靜態二叉檢索樹. (poj2482,poj2352)
樹狀樹組(poj1195,poj3321)
RMQ. (poj3264,poj3368)
並查集的高級應用. (poj1703,2492)
KMP演算法. (poj1961,poj2406)
四.搜索
最優化剪枝和可行性剪枝
搜索的技巧和優化 (poj3411,poj1724)
記憶化搜索(poj3373,poj1691)
五.動態規劃
較為復雜的動態規劃(如動態規劃解特別的旅行商TSP問題等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
記錄狀態的動態規劃. (POJ3254,poj2411,poj1185)
樹型動態規劃(poj2057,poj1947,poj2486,poj3140)
六.數學
組合數學:
1.容斥原理.
2.抽屜原理.
3.置換群與Polya定理(poj1286,poj2409,poj3270,poj1026).
4.遞推關系和母函數.
數學.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率問題. (poj3071,poj3440)
3.GCD、擴展的歐幾里德(中國剩餘定理) (poj3101)
計算方法.
1.0/1分數規劃. (poj2976)
2.三分法求解單峰(單谷)的極值.
3.矩陣法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
隨機化演算法(poj3318,poj2454)
雜題(poj1870,poj3296,poj3286,poj1095)
七.計算幾何學.
坐標離散化.
掃描線演算法(例如求矩形的面積和周長並,常和線段樹或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多邊形的內核(半平面交)(poj3130,poj3335)
幾何工具的綜合應用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高級（regional中等難度）:
一.基本演算法要求:
代碼快速寫成,精簡但不失風格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
保證正確性和高效性. poj3434
二.圖演算法:
度限制最小生成樹和第K最短路. (poj1639)
最短路,最小生成樹,二分圖,最大流問題的相關理論(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最優比率生成樹. (poj2728)
最小樹形圖(poj3164)
次小生成樹.
無向圖、有向圖的最小環
三.數據結構.
trie圖的建立和應用. (poj2778)
LCA和RMQ問題(LCA(最近公共祖先問題) 有離線演算法(並查集+dfs) 和 在線演算法(RMQ+dfs)).(poj1330)
雙端隊列和它的應用(維護一個單調的隊列,常常在動態規劃中起到優化狀態轉移的目的). (poj2823)
左偏樹(可合並堆).
後綴樹(非常有用的數據結構,也是賽區考題的熱點).(poj3415,poj3294)
四.搜索
較麻煩的搜索題目訓練(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
廣搜的狀態優化:利用M進制數存儲狀態、轉化為串用hash表判重、按位壓縮存儲狀態、雙向廣搜、A*演算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
深搜的優化:盡量用位運算、一定要加剪枝、函數參數盡可能少、層數不易過大、可以考慮雙向搜索或者是輪換搜索、IDA*演算法. (poj3131,poj2870,poj2286)
五.動態規劃
需要用數據結構優化的動態規劃.(poj2754,poj3378,poj3017)
四邊形不等式理論.
較難的狀態DP(poj3133)
六.數學
組合數學.
1.MoBius反演(poj2888,poj2154)
2.偏序關系理論.
博奕論.
1.極大極小過程(poj3317,poj1085)
2.Nim問題.
七.計算幾何學.
半平面求交(poj3384,poj2540)
可視圖的建立(poj2966)
點集最小圓覆蓋.
對踵點(poj2079)