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

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

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

3、j的值，表示從點(diǎn)i到點(diǎn)j的邊的權(quán)值，定義如下：上圖中的3個(gè)圖對(duì)應(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; /讀入兩個(gè)頂點(diǎn)序號(hào)及權(quán)值 gij = w; /對(duì)于不帶權(quán)的圖gij=1 gji = w; /無向圖的對(duì)稱性,如果是有向圖則不要有這句！ return 0;建立鄰接矩陣時(shí)，有兩個(gè)小技巧:初始化數(shù)組大可不必使用兩重for循環(huán)。1)如果是int數(shù)組，采用memset(g, 0 x7f, sizeof(g)可全部初始化為一個(gè)很大的數(shù)(略小于0 x7fffffff)，使用memset(g, 0, sizeof(g)，全部清為0，使用memset(g, 0 xaf, sizeof(g)，全部初始化為一個(gè)很小的數(shù)。 2)如果是double數(shù)組，采用memset(g,127,sizeof

5、(g);可全部初始化為一個(gè)很大的數(shù)1.38*10306，使用memset(g, 0, sizeof(g)全部清為0.2.數(shù)組模擬鄰接表存儲(chǔ)圖的鄰接表存儲(chǔ)法，又叫鏈?zhǔn)酱鎯?chǔ)法。本來是要采用鏈表實(shí)現(xiàn)的，但大多數(shù)情況下只要用數(shù)組模擬即可。以下是用數(shù)組模擬鄰接表存儲(chǔ)的參考程序段：#include using namespace std;const int maxn=1001,maxm=100001;struct Edgeint next; /下一條邊的編號(hào) int to; /這條邊到達(dá)的點(diǎn) 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); /讀入點(diǎn)數(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) /遍歷從點(diǎn)1開始的所有邊 /./.return 0;兩種方法各有用武之地，需按具體情況，具體選用。第二節(jié) 圖的遍歷一、深度優(yōu)先與廣度優(yōu)先遍歷從圖中某一頂點(diǎn)出發(fā)系統(tǒng)地訪問圖中所有頂點(diǎn)，使每個(gè)頂點(diǎn)恰好被訪問一次，這種運(yùn)算操作被稱為圖的遍歷。為了避免重復(fù)訪問某個(gè)頂點(diǎn)，可以設(shè)一個(gè)標(biāo)志數(shù)組visitedi，未訪問時(shí)值為false，訪問一次后就改為true。圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種方法，兩者的時(shí)間效率都是O(n*n)。1.深度優(yōu)先遍歷深度優(yōu)先遍歷與深搜DFS相似，從一個(gè)點(diǎn)A出發(fā)，將這個(gè)點(diǎn)標(biāo)為已訪問visitedi:=true;，然后再訪問所有與之相連，且未被訪問過

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

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

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

11、入了一次，顯然一定要出去一次，顯然是偶點(diǎn)。對(duì)于歐拉回路，每個(gè)點(diǎn)進(jìn)入和出去次數(shù)一定都是相等的，顯然沒有奇點(diǎn)。求歐拉路的算法很簡單，使用深度優(yōu)先遍歷即可。根據(jù)一筆畫的兩個(gè)定理，如果尋找歐拉回路，對(duì)任意一個(gè)點(diǎn)執(zhí)行深度優(yōu)先遍歷；找歐拉路，則對(duì)一個(gè)奇點(diǎn)執(zhí)行DFS，時(shí)間復(fù)雜度為O(m+n)，m為邊數(shù)，n是點(diǎn)數(shù)。以下是尋找一個(gè)圖的歐拉路的算法實(shí)現(xiàn)：樣例輸入:第一行n，m，有n個(gè)點(diǎn)，m條邊，以下m行描述每條邊連接的兩點(diǎn)。 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; /此圖用鄰接矩陣存儲(chǔ)int dumaxn; /記錄每個(gè)點(diǎn)的度，就是相連的邊的數(shù)目int circuitmaxn; /用來記錄找到的歐拉路的路徑int n,e,circuitpos,i,j,x,y,start;void find_circuit(int i) /這個(gè)點(diǎn)深度優(yōu)先遍歷過程尋找歐拉路 int j; for (j = 1; j n e; for (i = 1; i x y; gyx = gxy = 1; dux+; /統(tǒng)計(jì)每個(gè)點(diǎn)的度 duy+; start = 1; /如果有奇點(diǎn)，就從奇點(diǎn)開始尋找，這樣找到的就是 fo

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

14、回路，而哈密爾頓環(huán)是指不重復(fù)地走過所有的點(diǎn)，并且最后還能回到起點(diǎn)的回路。使用簡單的深度優(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ù)組模擬鄰接表存儲(chǔ)，訪問點(diǎn)i，

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