圖論算法(C++版)

1、第四章 圖論算法第一節(jié) 基本概念一、什么是圖？很簡單，點用邊連起來就叫做圖，嚴格意義上講，圖是一種數(shù)據(jù)結(jié)構，定義為：graph=（V，E）。V是一個非空有限集合，代表頂點（結(jié)點），E代表邊的集合。二、圖的一些定義和概念(a)有向圖：圖的邊有方向，只能按箭頭方向從一點到另一點。(a)就是一個有向圖。(b)無向圖：圖的邊沒有方向，可以雙向。(b)就是一個無向圖。結(jié)點的度：無向圖中與結(jié)點相連的邊的數(shù)目，稱為結(jié)點的度。結(jié)點的入度：在有向圖中，以這個結(jié)點為終點的有向邊的數(shù)目。結(jié)點的出度：在有向圖中，以這個結(jié)點為起點的有向邊的數(shù)目。權值：邊的“費用”，可以形象地理解為邊的長度。連通：如果圖中結(jié)點U，V之間

2、存在一條從U通過若干條邊、點到達V的通路，則稱U、V 是連通的?；芈罚浩瘘c和終點相同的路徑，稱為回路，或“環(huán)”。完全圖：一個n 階的完全無向圖含有n*(n-1)/2 條邊；一個n 階的完全有向圖含有n*(n-1)條邊；稠密圖：一個邊數(shù)接近完全圖的圖。稀疏圖：一個邊數(shù)遠遠少于完全圖的圖。強連通分量：有向圖中任意兩點都連通的最大子圖。右圖中，1-2-5構成一個強連通分量。特殊地，單個點也算一個強連通分量，所以右圖有三個強連通分量：1-2-5，4，3。 1 2 3 4 5 (a) 1 2 3 4 5 (b) 1 2 3 4 5 三、圖的存儲結(jié)構1.二維數(shù)組鄰接矩陣存儲定義int G101101;Gi

3、j的值，表示從點i到點j的邊的權值，定義如下：上圖中的3個圖對應的鄰接矩陣分別如下： 0 1 1 1 0 1 1 5 8 3G（A）= 1 0 1 1 G（B）= 0 0 1 5 2 6 1 1 0 0 0 1 0 G（C）= 8 2 10 4 1 1 0 0 10 11 3 6 4 11 下面是建立圖的鄰接矩陣的參考程序段：#includeusing namespace std;int i,j,k,e,n;double g101101;double w;int main() int i,j; for (i = 1; i = n; i+) for (j = 1; j e; for (k = 1

4、; k i j w; /讀入兩個頂點序號及權值 gij = w; /對于不帶權的圖gij=1 gji = w; /無向圖的對稱性,如果是有向圖則不要有這句！ return 0;建立鄰接矩陣時，有兩個小技巧:初始化數(shù)組大可不必使用兩重for循環(huán)。1)如果是int數(shù)組，采用memset(g, 0 x7f, sizeof(g)可全部初始化為一個很大的數(shù)(略小于0 x7fffffff)，使用memset(g, 0, sizeof(g)，全部清為0，使用memset(g, 0 xaf, sizeof(g)，全部初始化為一個很小的數(shù)。 2)如果是double數(shù)組，采用memset(g,127,sizeof

5、(g);可全部初始化為一個很大的數(shù)1.38*10306，使用memset(g, 0, sizeof(g)全部清為0.2.數(shù)組模擬鄰接表存儲圖的鄰接表存儲法，又叫鏈式存儲法。本來是要采用鏈表實現(xiàn)的，但大多數(shù)情況下只要用數(shù)組模擬即可。定義兩個數(shù)組，例如：int g101101;用來存儲這個圖。再定義一個一維數(shù)組：int num101;用來記錄與每個點相連的點的數(shù)目。如果邊有權值，還要定義一個數(shù)組int val101101存儲邊權。以下是用數(shù)組模擬鄰接表存儲的參考程序段：#includeusing namespace std;int n,m,i,j,c;int g101101;int num101;

6、int main() memset(g,0 x7f,sizeof(g); memset(num,0,sizeof(num); cinn; for (i = 1; i numi; /第i行說明點i的連接情況，每行的開頭讀入與之相連的點的數(shù)目 for (j = 1; j gij; /第j個與i相連的點是gij vali gij = v; /有權圖還要存下權值 return 0;兩種方法各有用武之地，需按具體情況，具體選用。第二節(jié) 圖的遍歷一、深度優(yōu)先與廣度優(yōu)先遍歷從圖中某一頂點出發(fā)系統(tǒng)地訪問圖中所有頂點，使每個頂點恰好被訪問一次，這種運算操作被稱為圖的遍歷。為了避免重復訪問某個頂點，可以設一個標志

7、數(shù)組visitedi，未訪問時值為false，訪問一次后就改為true。圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法，兩者的時間效率都是O(n*n)。1.深度優(yōu)先遍歷深度優(yōu)先遍歷與深搜DFS相似，從一個點A出發(fā)，將這個點標為已訪問visitedi:=true;，然后再訪問所有與之相連，且未被訪問過的點。當A的所有鄰接點都被訪問過后，再退回到A的上一個點（假設是B），再從B的另一個未被訪問的鄰接點出發(fā)，繼續(xù)遍歷。例如對右邊的這個無向圖深度優(yōu)先遍歷，假定先從1出發(fā)程序以如下順序遍歷：125，然后退回到2，退回到1。從1開始再訪問未被訪問過的點3 ，3沒有未訪問的鄰接點，退回1。再從1開始訪問未被

8、訪問過的點4，再退回1 。起點1的所有鄰接點都已訪問，遍歷結(jié)束。 1 2 3 4 5 下面給出的深度優(yōu)先遍歷的參考程序，假設圖以鄰接表存儲void dfs(int i) /圖用數(shù)組模擬鄰接表存儲，訪問點i visitedi = true; /標記為已經(jīng)訪問過 for (int j = 1; j = numi; j+) /遍歷與i相關聯(lián)的所有未訪問過的頂點 if (!visitedgij) dfs(gij); 主程序如下:int main() memset(visited,false,sizeof(visited); for (int i = 1; i = n; i+) /每一個點都作為起點嘗試

9、訪問，因為不是從任何 /一點開始都能遍歷整個圖的，例如下面的兩個圖。 if (!visitedi) dfs(i); return 0; 1 2 3 4 5 以3為起點根本不能遍歷整個圖這個非連通無向圖任何一個點為起點都不能遍歷整個圖 1 4 5 2 3 2.廣度優(yōu)先遍歷廣度優(yōu)先遍歷并不常用，從編程復雜度的角度考慮，通常采用的是深度優(yōu)先遍歷。廣度優(yōu)先遍歷和廣搜BFS相似，因此使用廣度優(yōu)先遍歷一張圖并不需要掌握什么新的知識，在原有的廣度優(yōu)先搜索的基礎上，做一點小小的修改，就成了廣度優(yōu)先遍歷算法。二、一筆畫問題如果一個圖存在一筆畫，則一筆畫的路徑叫做歐拉路，如果最后又回到起點，那這個路徑叫做歐拉回路

10、。我們定義奇點是指跟這個點相連的邊數(shù)目有奇數(shù)個的點。對于能夠一筆畫的圖，我們有以下兩個定理。定理1：存在歐拉路的條件：圖是連通的，有且只有2個奇點。定理2：存在歐拉回路的條件：圖是連通的，有0個奇點。兩個定理的正確性是顯而易見的，既然每條邊都要經(jīng)過一次，那么對于歐拉路，除了起點和終點外，每個點如果進入了一次，顯然一定要出去一次，顯然是偶點。對于歐拉回路，每個點進入和出去次數(shù)一定都是相等的，顯然沒有奇點。求歐拉路的算法很簡單，使用深度優(yōu)先遍歷即可。根據(jù)一筆畫的兩個定理，如果尋找歐拉回路，對任意一個點執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對一個奇點執(zhí)行DFS，時間復雜度為O(m+n)，m為邊數(shù)，n是點數(shù)。

11、 以下是尋找一個圖的歐拉路的算法實現(xiàn)： 樣例輸入:第一行n，m，有n個點，m條邊，以下m行描述每條邊連接的兩點。 5 5 1 2 2 3 3 4 4 5 5 1 樣例輸出:歐拉路或歐拉回路 1 5 4 3 2 1【參考程序】Euler.cpp#include#includeusing namespace std;#define maxn 101int gmaxnmaxn; /此圖用鄰接矩陣存儲int dumaxn; /記錄每個點的度，就是相連的邊的數(shù)目int circuitmaxn; /用來記錄找到的歐拉路的路徑int n,e,circuitpos,i,j,x,y,start;void fin

12、d_circuit(int i) /這個點深度優(yōu)先遍歷過程尋找歐拉路 int j; for (j = 1; j n e; for (i = 1; i x y; gyx = gxy = 1; dux+; /統(tǒng)計每個點的度 duy+; start = 1; /如果有奇點，就從奇點開始尋找，這樣找到的就是 for (i = 1; i = n; i+) /歐拉路。沒有奇點就從任意點開始， if (dui%2 = 1) /這樣找到的就是歐拉回路。(因為每一個點都是偶點) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i = cir

13、cuitpos; i+) cout circuiti ; cout endl; return 0; 注意以上程序具有一定的局限性，對于下面這種情況它不能很好地處理： 上圖具有多個歐拉回路，而本程序只能找到一個回路。讀者在遇到具體問題時，還應對程序作出相應的修改。三、哈密爾頓環(huán)歐拉回路是指不重復地走過所有路徑的回路，而哈密爾頓環(huán)是指不重復地走過所有的點，并且最后還能回到起點的回路。使用簡單的深度優(yōu)先搜索，就能求出一張圖中所有的哈密爾頓環(huán)。下面給出一段參考程序：#include#includeusing namespace std;int start,length,x,n; bool visite

14、d101,v1101;int ans101, num101;int g101101;void print() int i; for (i = 1; i = length; i+) cout ansi; cout endl; void dfs(int last,int i) /圖用數(shù)組模擬鄰接表存儲，訪問點i，last表示上次訪問的點 visitedi = true; /標記為已經(jīng)訪問過 v1i = true; /標記為已在一張圖中出現(xiàn)過 ans+length = i; /記錄下答案 for (int j = 1; j = numi; j+) if (gij=x&gij!=last) /

15、回到起點，構成哈密爾頓環(huán) ans+length = gij; print(); /這里說明找到了一個環(huán)，則輸出ans數(shù)組。length-;break; if (!visitedgij) dfs(i,gij); /遍歷與i相關聯(lián)的所有未訪問過的頂點 length-; visitedi = false; /這里是回溯過程，注意v1的值不恢復。 int main() memset(visited,false,sizeof(visited); memset(v1,false,sizeof(v1); for (x = 1; x = n; x+) /每一個點都作為起點嘗試訪問，因為不是從任何一點開始都能找

16、過整個圖的 if (!v1x) /如果點x不在之前曾經(jīng)被訪問過的圖里。 length = 0; /定義一個ans數(shù)組存答案，length記答案的長度。 dfs(x); return 0;【上機練習】1、珍珠BEAD【問題描述】有n顆形狀和大小都一致的珍珠，它們的重量都不相同。n為整數(shù)，所有的珍珠從1到n編號。你的任務是發(fā)現(xiàn)哪顆珍珠的重量剛好處于正中間，即在所有珍珠的重量中，該珍珠的重量列(n+1)/2位。下面給出將一對珍珠進行比較的辦法：給你一架天平用來比較珍珠的重量，我們可以比出兩個珍珠哪個更重一些，在作出一系列的比較后，我們可以將某些肯定不具備中間重量的珍珠拿走。例如，下列給出對5顆珍珠進行四次比較的情況：1、珍珠2比珍珠1重2、珍珠4比珍珠3重3、珍珠5比珍珠1重4、珍珠4比珍珠2重根據(jù)以上結(jié)果，雖然我們不能精確地找出哪個珍珠具有中間重量，但我們可以肯定珍珠1和珍珠4不可能具有中間重量，因為珍珠2、4、5比珍珠1重，而珍珠1、2、3比珍珠4輕，所以我們可以移走這兩顆珍珠。寫一個程序統(tǒng)計出共有多少顆珍珠肯定不會是中間重量?！据斎敫袷健枯斎胛募谝恍邪瑑蓚€用空格隔開的整數(shù)N和M，其中1=N=1)個柵欄。所有柵欄都是連通的(也就是你可以從任意一個柵欄到達另外的所有柵欄)。 你的程序必須輸出騎馬的路徑(用路上依次經(jīng)過的頂點號碼表示)。我們?nèi)绻演敵龅穆窂娇?/p>