第4章第1-2節(jié) 圖論算法(C版)

1、第四章 圖論算法第一節(jié) 基本概念一、什么是圖？很簡單，點用邊連起來就叫做圖，嚴(yán)格意義上講，圖是一種數(shù)據(jù)結(jié)構(gòu)，定義為：graph=（V，E）。V是一個非空有限集合，代表頂點（結(jié)點），E代表邊的集合。二、圖的一些定義和概念(a)有向圖：圖的邊有方向，只能按箭頭方向從一點到另一點。(a)就是一個有向圖。(b)無向圖：圖的邊沒有方向，可以雙向。(b)就是一個無向圖。結(jié)點的度：無向圖中與結(jié)點相連的邊的數(shù)目，稱為結(jié)點的度。結(jié)點的入度：在有向圖中，以這個結(jié)點為終點的有向邊的數(shù)目。結(jié)點的出度：在有向圖中，以這個結(jié)點為起點的有向邊的數(shù)目。權(quán)值：邊的“費用”，可以形象地理解為邊的長度。連通：如果圖中結(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構(gòu)成一個強連通分量。特殊地，單個點也算一個強連通分量，所以右圖有三個強連通分量：1-2-5，4，3。 1 2 3 4 5 (a) 1 2 3 4 5 (b) 1 2 3 4 5 三、圖的存儲結(jié)構(gòu)1.二維數(shù)組鄰接矩陣存儲定義int G101101;Gi

3、j的值，表示從點i到點j的邊的權(quán)值，定義如下：上圖中的3個圖對應(yīng)的鄰接矩陣分別如下： 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; /讀入兩個頂點序號及權(quán)值 gij = w; /對于不帶權(quán)的圖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ù)組模擬鄰接表存儲圖的鄰接表存儲法，又叫鏈?zhǔn)酱鎯Ψ?。本來是要采用鏈表實現(xiàn)的，但大多數(shù)情況下只要用數(shù)組模擬即可。以下是用數(shù)組模擬鄰接表存儲的參考程序段：#include using namespace std;const int maxn=1001,maxm=100001;struct Edgeint next; /下一條邊的編號 int to; /這條邊到達的點 int dis; /這條邊的長度 edgemaxm;int headmaxn,num_edge,n,m,u,v,d

6、;void add_edge(int from,int to,int dis) /加入一條從from到to距離為dis的單向邊 edge+num_edge.next=headfrom;edgenum_edge.to=to;edgenum_edge.dis=dis;headfrom=num_edge;int main()num_edge=0;scanf(%d %d,&n,&m); /讀入點數(shù)和邊數(shù)for(int i=1;i=m;i+) scanf(%d %d %d,&u,&v,&d); /u、v之間有一條長度為d的邊 add_edge(u,v,d);for(int i=head1;i!=0;i=

7、edgei.next) /遍歷從點1開始的所有邊 /./.return 0;兩種方法各有用武之地，需按具體情況，具體選用。第二節(jié) 圖的遍歷一、深度優(yōu)先與廣度優(yōu)先遍歷從圖中某一頂點出發(fā)系統(tǒng)地訪問圖中所有頂點，使每個頂點恰好被訪問一次，這種運算操作被稱為圖的遍歷。為了避免重復(fù)訪問某個頂點，可以設(shè)一個標(biāo)志數(shù)組visitedi，未訪問時值為false，訪問一次后就改為true。圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法，兩者的時間效率都是O(n*n)。1.深度優(yōu)先遍歷深度優(yōu)先遍歷與深搜DFS相似，從一個點A出發(fā)，將這個點標(biāo)為已訪問visitedi:=true;，然后再訪問所有與之相連，且未被訪問過

8、的點。當(dāng)A的所有鄰接點都被訪問過后，再退回到A的上一個點（假設(shè)是B），再從B的另一個未被訪問的鄰接點出發(fā)，繼續(xù)遍歷。例如對右邊的這個無向圖深度優(yōu)先遍歷，假定先從1出發(fā)程序以如下順序遍歷：125，然后退回到2，退回到1。從1開始再訪問未被訪問過的點3 ，3沒有未訪問的鄰接點，退回1。再從1開始訪問未被訪問過的點4，再退回1 。起點1的所有鄰接點都已訪問，遍歷結(jié)束。 1 2 3 4 5 下面給出的深度優(yōu)先遍歷的參考程序，假設(shè)圖以鄰接表存儲void dfs(int i) /圖用數(shù)組模擬鄰接表存儲，訪問點i visitedi = true; /標(biāo)記為已經(jīng)訪問過 for (int j = 1; j =

9、numi; j+) /遍歷與i相關(guān)聯(lián)的所有未訪問過的頂點 if (!visitedgij) dfs(gij); 主程序如下:int main() memset(visited,false,sizeof(visited); for (int i = 1; i = n; i+) /每一個點都作為起點嘗試訪問，因為不是從任何 /一點開始都能遍歷整個圖的，例如下面的兩個圖。 if (!visitedi) dfs(i); return 0; 1 2 3 4 5 以3為起點根本不能遍歷整個圖這個非連通無向圖任何一個點為起點都不能遍歷整個圖 1 4 5 2 3 2.廣度優(yōu)先遍歷廣度優(yōu)先遍歷并不常用，從編程復(fù)

10、雜度的角度考慮，通常采用的是深度優(yōu)先遍歷。廣度優(yōu)先遍歷和廣搜BFS相似，因此使用廣度優(yōu)先遍歷一張圖并不需要掌握什么新的知識，在原有的廣度優(yōu)先搜索的基礎(chǔ)上，做一點小小的修改，就成了廣度優(yōu)先遍歷算法。二、一筆畫問題如果一個圖存在一筆畫，則一筆畫的路徑叫做歐拉路，如果最后又回到起點，那這個路徑叫做歐拉回路。我們定義奇點是指跟這個點相連的邊數(shù)目有奇數(shù)個的點。對于能夠一筆畫的圖，我們有以下兩個定理。定理1：存在歐拉路的條件：圖是連通的，有且只有2個奇點。定理2：存在歐拉回路的條件：圖是連通的，有0個奇點。兩個定理的正確性是顯而易見的，既然每條邊都要經(jīng)過一次，那么對于歐拉路，除了起點和終點外，每個點如果進

11、入了一次，顯然一定要出去一次，顯然是偶點。對于歐拉回路，每個點進入和出去次數(shù)一定都是相等的，顯然沒有奇點。求歐拉路的算法很簡單，使用深度優(yōu)先遍歷即可。根據(jù)一筆畫的兩個定理，如果尋找歐拉回路，對任意一個點執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對一個奇點執(zhí)行DFS，時間復(fù)雜度為O(m+n)，m為邊數(shù)，n是點數(shù)。以下是尋找一個圖的歐拉路的算法實現(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

12、std;#define maxn 101int gmaxnmaxn; /此圖用鄰接矩陣存儲int dumaxn; /記錄每個點的度，就是相連的邊的數(shù)目int circuitmaxn; /用來記錄找到的歐拉路的路徑int n,e,circuitpos,i,j,x,y,start;void find_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; /如果有奇點，就從奇點開始尋找，這樣找到的就是 fo

13、r (i = 1; i = n; i+) /歐拉路。沒有奇點就從任意點開始， if (dui%2 = 1) /這樣找到的就是歐拉回路。(因為每一個點都是偶點) start = i; circuitpos = 0; find_circuit(start); for (i = 1; i = circuitpos; i+) cout circuiti ; cout endl; return 0;注意以上程序具有一定的局限性，對于下面這種情況它不能很好地處理：上圖具有多個歐拉回路，而本程序只能找到一個回路。讀者在遇到具體問題時，還應(yīng)對程序作出相應(yīng)的修改。三、哈密爾頓環(huán)歐拉回路是指不重復(fù)地走過所有路徑的

14、回路，而哈密爾頓環(huán)是指不重復(fù)地走過所有的點，并且最后還能回到起點的回路。使用簡單的深度優(yōu)先搜索，就能求出一張圖中所有的哈密爾頓環(huán)。下面給出一段參考程序：#include#includeusing namespace std;int start,length,x,n; bool visited101,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，

15、last表示上次訪問的點 visitedi = true; /標(biāo)記為已經(jīng)訪問過 v1i = true; /標(biāo)記為已在一張圖中出現(xiàn)過 ans+length = i; /記錄下答案 for (int j = 1; j = numi; j+) if (gij=x&gij!=last) /回到起點，構(gòu)成哈密爾頓環(huán) ans+length = gij; print(); /這里說明找到了一個環(huán)，則輸出ans數(shù)組。length-;break; if (!visitedgij) dfs(i,gij); /遍歷與i相關(guān)聯(lián)的所有未訪問過的頂點 length-; visitedi = false; /這里是回溯過程，注意v1的值不恢復(fù)。 int main() memset(visited,false,sizeof(visited); memset(v1,false,sizeof(v1); for (x = 1; x =1)個柵欄。所有柵欄都是連通的(也就是你可以從任意一個柵欄到達另外的所有柵欄)。 你的程序必須輸出騎馬的路徑(用路上依次經(jīng)過的頂點號碼表示)。我們?nèi)绻演敵龅穆窂娇闯墒且粋€500進制的數(shù)，那么當(dāng)存在多組解的情況下，輸出500進制表示法中最小的一個 (也就是輸出第一個數(shù)較小的，如果還有多組解，輸出第