圖及其應(yīng)用一

1、圖及其應(yīng)用一2、無向圖和有向圖無向圖： 在圖G=V，E中，假設(shè)對于任意的a，bV，當(dāng)(a，b)E時(shí)，必有b，aE即關(guān)系R對稱，對稱圖為無向圖。在一無向圖中用不帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的頂點(diǎn)。 V=V1,V2,V3,V4,V5 E=(V1,V2),(V2,V3),(V3,V4),(V4,V5),(V5,V1),(V2,V5),(V4,V1) 有向圖：假設(shè)對于任意的a，bV，當(dāng)(a，b)E時(shí) ，(b，a)E未必成立，那么稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)。V=V1,V2,V3,V4 E=, 頂點(diǎn)的度：無向圖：與頂點(diǎn)關(guān)聯(lián)的邊的數(shù)目。有向圖：等于該頂點(diǎn)的入度與出度之和。入

2、度以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和出度以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和 度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。3、頂點(diǎn)的度 練習(xí)題: 1. 假設(shè)我們用d=(a1,a2,.,a5),表示無向圖G的5個(gè)頂點(diǎn)的度數(shù)，下面給出的哪些組d 值合理 。 A5，4，4，3，1 B4，2，2，1，1 C3，3，3，2，2 D5，4，3，2，1 E2，2，2，2，22.無向圖G有16條邊，有3個(gè)4度頂點(diǎn)、4個(gè)3度頂點(diǎn)，其余頂點(diǎn)的度均小于3，那么G至少_個(gè)頂點(diǎn)。4、 途徑和連通集 在圖G=V，E中，假設(shè)對于結(jié)點(diǎn)a，b，存在滿足下述條件的結(jié)點(diǎn)序列x1xk(k1) x1=a，xk=b (xi，xi+1)E i=1k-

3、1那么稱結(jié)點(diǎn)序列x1=a，x2，xk=b為結(jié)點(diǎn)a到結(jié)點(diǎn)b的一條途徑，而途徑上邊的數(shù)目k-1或者沿途徑各邊權(quán)值之和稱為該途徑的長度，并稱結(jié)點(diǎn)集合x1，xk為連通集。V1, v2, v5, v45、簡單途徑和回路假設(shè)一條途徑上的結(jié)點(diǎn)除起點(diǎn)x1和終點(diǎn)xk可以一樣外，其它結(jié)點(diǎn)均不一樣，那么稱此途徑為一條簡單途徑。圖(a)中v1v2v3是一條簡單途徑，v1v3v4v1v3不是簡單途徑。x1=xk的簡單途徑稱為回路也稱為環(huán)。例如圖(b)中，v1v2v1為一條回路。例157324G26例245136G1途徑：1，2，3，5，6，3途徑長度：5簡單途徑：1，2，3，5回路：3，5，6，3途徑：1，2，5，7，

4、6，5，2，3途徑長度：7簡單途徑：1，2，5，7，6回路：1，2，3，1二、圖的存儲(chǔ)構(gòu)造教材P79圖的鄰接矩陣表示法 鄰接矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。假設(shè)G=V，E是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，那么G的鄰接矩陣是如下定義的二維數(shù)組a，其規(guī)模為n*n 1(或權(quán)值) 表示 頂點(diǎn)i和頂點(diǎn)j有邊(i和j的路程) Aij = 0或 表示頂點(diǎn)i和頂點(diǎn)j無邊 二維數(shù)組的行、列號表示頂點(diǎn)編號上圖中的圖G1和圖G2對應(yīng)的相鄰矩陣分別為： 無向帶權(quán)圖的鄰接(代價(jià))矩陣表示有向無權(quán)圖的鄰接矩陣表示鄰接矩陣的特點(diǎn)： 1)無向圖的鄰接矩陣是對稱的，而有向圖那么不是。2)鄰接矩陣方便度數(shù)的計(jì)算。用鄰接矩陣表示圖: (1)

5、容易斷定任意兩個(gè)結(jié)點(diǎn)之間是否有邊相聯(lián); (2)容易求得各個(gè)結(jié)點(diǎn)的度數(shù)。 對于無權(quán)無向圖的鄰接矩陣，第i行元素值的和就是Vi的度數(shù)； 對于無權(quán)有向圖的鄰接矩陣，第i行元素值的和就是Vi的出度，第i列元素值的和就是Vi的入度； 對于有權(quán)無向圖的鄰接矩陣，第i行或第i列中元素值0的元素個(gè)數(shù)就是Vi的度數(shù)； 對于有權(quán)有向圖的鄰接矩陣，第i行中元素值0的元素個(gè)數(shù)就是Vi的出度；第i列元素值0的元素個(gè)數(shù)就是Vi的入度。例1452375318642各頂點(diǎn)的度是多少？0618360240120078400530750讀入數(shù)據(jù)構(gòu)造鄰接矩陣P80競賽題中一般圖的數(shù)據(jù)是以這種方式給出的：題中會(huì)指定頂點(diǎn)數(shù)的最大值，以

6、便于定義一個(gè)全局二維數(shù)組作為鄰接矩陣數(shù)據(jù)文件的第1行一般是圖的頂點(diǎn)個(gè)數(shù)N以及邊數(shù)M接下來一般有M行，每行有2個(gè)或3個(gè)整數(shù)，描繪了每條邊的信息：假設(shè)是2個(gè)整數(shù)i，j，那么一般表示頂點(diǎn)i和頂點(diǎn)j有一條邊相連假設(shè)是3個(gè)整數(shù)i，j，k，那么一般表示頂點(diǎn)i和頂點(diǎn)j相連的權(quán)值為k針對圖數(shù)據(jù)的這種構(gòu)造，我們會(huì)用如下的代碼來構(gòu)造鄰接矩陣：const int MAXN = 201; /最大頂點(diǎn)數(shù)int aMAXNMAXN, n, m, i, j, k, x;scanf(%d%d, &n, &m);for (i=1; i=m; i+) /讀入m條邊scanf(%d%d, &j, &k);ajk = 1; /假設(shè)是

7、有向圖，那么只賦值ajkakj = 1; /假設(shè)是無向圖，那么一定要賦值akj假設(shè)是構(gòu)造帶權(quán)圖，那么上述for 語句中的代碼改為： scanf(%d%d, &j, &k, &x);ajk = x; /假設(shè)是有向圖，那么只賦值ajkakjl = x; /假設(shè)是無向圖，那么一定要賦值akj鄰接矩陣主對角線元素的處理在競賽中很少有圖數(shù)據(jù)是頂點(diǎn)帶自環(huán)邊的，因此鄰接矩陣的主對角線元素aii(1=i=n)一般都是0。在前面講的鄰接矩陣的構(gòu)造方法中，假設(shè)頂點(diǎn)i，j之間沒有邊，那么aij也表示為0。在大多數(shù)圖的算法中，不區(qū)別這兩種值為0的情況是可以的。而在某些圖算法中，必需要區(qū)別主對角線元素和其它非主對角線元

8、素，這時(shí)就用另外的特殊值來表示無邊相連的情況。特殊值一般取一個(gè)很大的正數(shù)或負(fù)數(shù)，實(shí)現(xiàn)實(shí)現(xiàn)代碼如下：const int BIG = 99999999; /表示無窮大for (i=1; i=n; i+) /初始化 for (j=1; j=n; j+) aij = BIG;aii = 0;for (i=1; i=m; i+) /讀入邊數(shù)據(jù)scanf(%d%d%d, &j, &k, &x);ajk = x;akj = x; /這句無向圖才要 鄰接矩陣的優(yōu)缺點(diǎn)見教材P80判斷i，j有無邊相連：O(1)找i的鄰接點(diǎn)，計(jì)算入度、出度：O(n)空間復(fù)雜性高：O(n2)邊集數(shù)組表示法教材P80一個(gè)一維數(shù)組存儲(chǔ)圖

9、每個(gè)元素表示一條邊：起點(diǎn)、終點(diǎn)、權(quán)值假設(shè)有的話適用于：對邊進(jìn)展依次處理的算法，適宜存儲(chǔ)頂點(diǎn)多但邊很少的稀疏圖缺點(diǎn)：判斷i，j有無邊相連：O(E)找i的鄰接點(diǎn)，計(jì)算入度、出度：O(E)優(yōu)點(diǎn)：構(gòu)造簡單邊集數(shù)組表示法的實(shí)現(xiàn)const int MAXEDGE = 2000;struct node int s , t; /邊的起點(diǎn)和終點(diǎn)int w; /邊的權(quán)值node edgeMAXEDGE;int n, m, i, j, k, x;scanf(%d%d, &n, &m);for (i=1; i=m; i+)scanf(%d%d%d, &j, &k, &x);edgei.s = j;edgei.t =

10、k;edgei.w = x;鄰接表表示法P81鄰接表表示法是指對圖中的每個(gè)頂點(diǎn)Vi(1=i=n)建立一個(gè)鄰接關(guān)系的單鏈表，并把它們的表頭指針用一維數(shù)組存儲(chǔ)起來的一種表示方法。為每個(gè)頂點(diǎn)Vi建立的單鏈表，是表示以該頂點(diǎn)為起點(diǎn)的所有邊的信息。以以以下圖教材圖52為例，頂點(diǎn)v1與v2、v3、v5相鄰，因此在v1的單鏈表里就包含3條邊的信息。v1v2v3v4v5524101183253853頂點(diǎn)v1的單鏈表有3個(gè)結(jié)點(diǎn)，表示有3條邊與v1相接，有3個(gè)頂點(diǎn)v2、v3、v5是v1的鄰接點(diǎn)不表示v2與v3相鄰，v3與v5相鄰鄰接表表示法P81一維指針數(shù)組存儲(chǔ)了每個(gè)頂點(diǎn)的單鏈表的頭指針。一般就用數(shù)組下標(biāo)表示了起

11、點(diǎn)編號。例如v1單鏈表的頭指針就存儲(chǔ)在adj1中。以以下圖的完好鄰接表如下所示：v1v2v3v4v552410118325385315325618225431051113265114103412345鄰接表的數(shù)據(jù)構(gòu)造const int MAXV = 201; /最大頂點(diǎn)數(shù)struct node int v; /鄰接點(diǎn)序號 int wt; /權(quán)值，假設(shè)是帶權(quán)圖的話 node *next; /鄰接單鏈表指針;node * adjMAXV; /每個(gè)頂點(diǎn)建一個(gè)單鏈表構(gòu)造鄰接表int n, m; /n表示讀入的頂點(diǎn)個(gè)數(shù)，m表示讀入的邊條數(shù)創(chuàng)立鄰接表void createlist() /創(chuàng)立鄰接表 int

12、 i,j,k,x; node *p; scanf(%d%d, &n, &m); /讀入頂點(diǎn)數(shù)和邊數(shù) for (i=1; i=n; i+) /初始化每個(gè)頂點(diǎn)的邊表為NULL adji = NULL; for (i=1; iv = k; /j的鄰接點(diǎn)是k p-wt = x; /邊的權(quán)值是x p-next = adjj; /新節(jié)點(diǎn)插在頂點(diǎn)j的邊表的表頭位置 adjj = p; /以下是無向圖需要構(gòu)造的對稱邊 p = new node; p-v = j; /k的鄰接點(diǎn)是j p-wt = x; p-next = adjk; /新節(jié)點(diǎn)插在頂點(diǎn)k的邊表的表頭位置 adjk = p; 鄰接表的優(yōu)缺點(diǎn)P82便于

13、查找后繼頂點(diǎn)、以該點(diǎn)為起點(diǎn)的邊、出度。不便于查找前趨頂點(diǎn)、以該點(diǎn)為終點(diǎn)的邊、入度。解決方法：建立逆鄰接表，即把以某頂點(diǎn)為終點(diǎn)的頂點(diǎn)放在一個(gè)單鏈表中。和鄰接矩陣相比，構(gòu)造鄰接表的編程復(fù)雜性要高一些，但是查找后繼頂點(diǎn)的效率要高O(e/n) vs. O(n)。假設(shè)邊比較稀疏，顯然用鄰接表存儲(chǔ)圖比較好。編程練習(xí)求一個(gè)有向圖中指定頂點(diǎn)的出度。輸入數(shù)據(jù)：第1行：2個(gè)空格分開的整數(shù)n(2=n=200)和m(10=m=20000)，分別表示圖的頂點(diǎn)數(shù)和邊數(shù)。第2.m+1行：每行2個(gè)空格分開的整數(shù)i，j，i表示一條邊的起點(diǎn)，j表示終點(diǎn)。第m2行：1個(gè)整數(shù)k(2=k=n),表示指定的頂點(diǎn)。輸出數(shù)據(jù)：第1行：1個(gè)整

14、數(shù)od，表示頂點(diǎn)k的出度。要求：分別用鄰接矩陣和鄰接表存儲(chǔ)圖。三、圖的遍歷給出一個(gè)圖G和其中任意一個(gè)結(jié)點(diǎn)V，從V出發(fā)訪問G中所有結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)被訪問一次不是只經(jīng)過一次，這就叫圖的遍歷。 通常有兩種遍歷方法： 深度優(yōu)先搜索dfs 廣度優(yōu)先搜索bfs 1、深度優(yōu)先搜索DFS方法：從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)；然后依次從V1的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V1相通的頂點(diǎn)都被訪問到；假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。為了防止重復(fù)訪問某個(gè)頂點(diǎn)，設(shè)一個(gè)標(biāo)志數(shù)組visit，頂點(diǎn)i未訪問時(shí)，visiti

15、的值為false，訪問后就改為true。V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7可以從任一頂點(diǎn)出發(fā)進(jìn)展DFSV1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5在程序中實(shí)現(xiàn)深度優(yōu)先搜索算法: 從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)；然后依次從V1的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V1相通的頂點(diǎn)都被訪問到。如何判別V

16、的鄰接點(diǎn)是否被訪問？解決的方法是:為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問標(biāo)志 visiti假設(shè)圖不連通，那么一次DFS只能訪問所有與V1連通的頂點(diǎn)。要對整個(gè)圖進(jìn)展遍歷，那么需要再任找一個(gè)尚未訪問的頂點(diǎn)，再次DFS，直到所有頂點(diǎn)均被訪問為止。abchdekfg812345670F F F F F F F F F0 1 2 3 4 5 6 7 8TTTTTTTTTachdkfe bgachkfedbg訪問標(biāo)志:訪問次序:例如:achdkfe參考代碼/從頂點(diǎn)i出發(fā)進(jìn)展深度優(yōu)先搜索,鄰接表實(shí)現(xiàn)/適用于有向圖和無向圖void dfs(int i) node *p; cout v = false) /假設(shè)鄰接點(diǎn)未訪問

17、 dfs(p-v); /那么對其遞歸DFS p = p-next; /取下一個(gè)鄰接點(diǎn) 參考代碼void dfstravel() /對圖進(jìn)展深度優(yōu)先遍歷 int i; memset(visit, 0, sizeof(visit); /清訪問標(biāo)志 for (i=1; i=n; i+) if (!visiti) dfs(i);DFS的應(yīng)用1、犯罪團(tuán)伙 警察抓到了n個(gè)罪犯，警察根據(jù)經(jīng)歷知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過警察的審訊，知道其中的一些罪犯之間互相認(rèn)識，同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識。有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請你根據(jù)罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。罪犯的

18、編號從1至n。輸入：第一行：n=5000,罪犯數(shù)量，m50000，關(guān)系數(shù)量以下m行：每行兩個(gè)數(shù)：i 和j，中間一個(gè)空格隔開，表示罪犯i和罪犯j互相認(rèn)識。輸出：一個(gè)整數(shù)，犯罪團(tuán)伙的數(shù)量。樣例輸入：11 8 1 24 35 41 35 67 105 108 9輸出：3說明：共三個(gè)犯罪團(tuán)伙。分析把人處理成頂點(diǎn)，把認(rèn)識關(guān)系處理成邊，犯罪團(tuán)伙構(gòu)成一個(gè)圖有向還是無向？那么根據(jù)輸入數(shù)據(jù)可以構(gòu)造一個(gè)鄰接表可以用鄰接矩陣嗎？假設(shè)不能請說明原因。從1到n枚舉頂點(diǎn)Vi，從Vi進(jìn)展DFS，那么能找到一個(gè)團(tuán)伙。然后再另選一個(gè)未訪問的頂點(diǎn)，再次DFS，直到所有頂點(diǎn)均被訪問。最后，調(diào)用DFS的次數(shù)就是團(tuán)伙的個(gè)數(shù)。const

19、 maxn=1000;var a:array1.maxn,1.maxnof longint; visited:array1.maxnof 0.1; t:array1.maxnof char; n,m,i,s:longint; procedure init; var i,x,y:longint; begin assign(input,group5.in);reset(input); readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; close(input); end;procedure

20、 dfs(i:longint); var j:longint; begin visitedi:=1; for j:=1 to n do if (ai,j=1) and (visitedj=0) then dfs(j); end;Begin init; s:=0; for i:=1 to n do visitedi:=0; for i:=1 to n do if visitedi=0 then begin dfs(i); inc(s); end; writeln(s); end.12354672、哈密頓路 郵遞員在送信時(shí)，為了節(jié)省路途，自己規(guī)定：每次總是從n個(gè)村子中選擇其中一個(gè)適宜的村子出發(fā)，途

21、經(jīng)每個(gè)村子僅且經(jīng)過一次，送完所有的信。各個(gè)村子的道路連通情況。請你幫郵遞員選擇一條適宜的道路。輸入：第一行：整數(shù)n(2=n=200)：村子的個(gè)數(shù)。接下來是一個(gè)n*n的0、1矩陣，表示n個(gè)村子的連同情況，如：ai,j=1 ，表示第i和第j個(gè)村子之間有路可走，假設(shè)ai,j=0，表示他們之間無路可走。輸出：一條可行的道路輸入：70 1 0 1 1 0 01 0 1 0 1 0 00 1 0 0 0 0 11 0 0 0 0 0 01 1 0 0 0 1 00 0 0 0 1 0 10 0 1 0 0 1 0輸出：2 3 7 6 5 1 4分析題目的限制條件：“途經(jīng)每個(gè)村子僅且經(jīng)過一次，說明在深搜的過

22、程中，Vi的鄰接點(diǎn)中必需要有至少一個(gè)頂點(diǎn)是沒有被訪問過的。這樣才能沿著該點(diǎn)繼續(xù)DFS下去。假設(shè)恰能遍歷全部結(jié)點(diǎn)，那么找到一條途徑，輸出這條途徑即可。怎樣在DFS的過程中保存途徑？假設(shè)在DFS的某一層出現(xiàn)了所有鄰接點(diǎn)都被訪問過了，那么說明在上一層以及更上層的路由選擇不正確，這時(shí)就要回溯到上層，換一個(gè)未被訪問的結(jié)點(diǎn),再次進(jìn)展DFS，看能否走通。在換結(jié)點(diǎn)的時(shí)候，一定要去除前一個(gè)結(jié)點(diǎn)被訪問過的標(biāo)志信息，這就是所謂的“清理現(xiàn)場的工作。假設(shè)不做這個(gè)操作，那么求解幾乎沒有可能得到正確結(jié)果。const maxn=100;算法一var a:array1.maxn,1.maxnof integer; visite

23、d:array1.maxnof 0.1; b:array1.maxn of 1.maxn; n,m,i:integer; found:integer; procedure init; var i,j:integer; begin assign(input,a.in);reset(input); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); close(input); end; procedure print; var i:integer; begin found:=1; for i:=1 to n-1 do write(bi,

24、 ); writeln(bn); end; procedure dfs(i:integer); var j,k:integer; begin /m是當(dāng)前訪問的結(jié)點(diǎn)個(gè)數(shù) if m = n then begin print; exit; end; for j:=1 to n do if (aj,i=1) and (visitedj=0) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj:=0; m:=m-1; end; end; Begin init; found:=0; for i:= 1 to n do begin fillchar

25、(visited,sizeof(visited),0); m:=1; b1:=i; visitedi:=1; dfs(i); end; if found=0 then writeln(no road); end.算法二procedure dfs(i,k:integer); 結(jié)點(diǎn)i是路上的第k個(gè)結(jié)點(diǎn) var j:integer; begin if k=n then print; for j:=1 to n do if (aj,i=1) and (visitedj=0) then begin visitedj:=1; bk+1:=j; dfs(j,k+1); visitedj:=0; end; e

26、nd;Begin init; found:=0; for i:= 1 to n do begin fillchar(visited,sizeof(visited),0); m:=1; b1:=i; visitedi:=1; dfs(i,1); end; if found=0 then writeln(no road); end.3 、安排座位 n個(gè)客人圍著一個(gè)桌子吃飯，每一個(gè)人都至少認(rèn)識其他的2個(gè)客人。請?jiān)O(shè)計(jì)程序求得n個(gè)人的一種坐法，使得每個(gè)人都認(rèn)識他左右的客人。輸入:第一行:n吃飯人的個(gè)數(shù)。以下n行：第i行的第一個(gè)數(shù)k表示第i個(gè)人認(rèn)識的人數(shù)，后面k個(gè)數(shù)依次為i認(rèn)識的人的編號。輸出：所有座法，

27、要求第一個(gè)人為1號作為起點(diǎn)，按順時(shí)針輸出其它人的編號。樣例輸入：62 3 63 4 5 63 1 4 63 2 3 53 2 4 64 1 2 3 5樣例輸出：1 3 4 2 5 61 3 4 5 2 61 6 2 5 4 31 6 5 2 4 3分析: 假設(shè)A認(rèn)識B,B又認(rèn)識C,那么B認(rèn)識他左右的兩個(gè)人.繼續(xù)這個(gè)過程,假設(shè)C又認(rèn)識D,那么C認(rèn)識他左右的兩個(gè)人;這其實(shí)就是一個(gè)DFS過程.假設(shè)最后一個(gè)人能認(rèn)識第一個(gè)人,那么最后一個(gè)人也認(rèn)識他左右的兩個(gè)人.這樣就找到一組滿足要求的解了.此題是求一個(gè)N個(gè)頂點(diǎn)的簡單回路問題.procedure dfs(i:integer); var j,k:integ

28、er; begin if (n=m)and(ab1,bm=1) then print; for j:=1 to n do if (ai,j=1) and (visitedj=0) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj:=0; m:=m-1; end; end;Begin init; fillchar(visited,sizeof(visited),0); found:=0; m:=1; b1:=1; visited1:=1; dfs(1); if found=0 then writeln(no road); end.4、

29、素?cái)?shù)鏈設(shè)計(jì)程序?qū)?,2,20排成一排，使任意兩個(gè)相鄰的數(shù)的和為素?cái)?shù)。第1個(gè)和最后一個(gè)的和也為素?cái)?shù).輸出:120個(gè)數(shù)的排列方式.const maxn=100;var visited:array1.maxnof 0.1; b:array1.maxn of 1.maxn; n,m,i:integer; found:integer; function check(i:integer):boolean; var j:integer; begin for j:=2 to i-1 do if i mod j=0 then begin check:=false; exit; end; check:=true;

30、 end; procedure print; var i:integer; begin found:=1; for i:=1 to n-1 do write(bi, ); writeln(bn); halt; end; procedure dfs(i:integer); var j,k:integer; begin if (m=n)and(check(b1+bm) then print; for j:=1 to n do if (visitedj=0) and (check(i+j) then begin visitedj:=1; m:=m+1; bm:=j; dfs(j); visitedj

31、:=0; m:=m-1; end; end;Begin fillchar(visited,sizeof(visited),0); n:=20; found:=0; m:=1; b1:=1; visited1:=1; dfs(1); if found=0 then writeln(no road); end.2、廣度寬度優(yōu)先搜索BFS 廣度優(yōu)先搜索按層次遍歷的過程，其搜索過程如下：方法：從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)后，依次訪問V1的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；假設(shè)此時(shí)圖中尚有頂點(diǎn)未被訪問，那么另選圖中一個(gè)未

32、被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V5在程序中實(shí)現(xiàn)BFS從圖的某一頂點(diǎn)V1出發(fā)，訪問此頂點(diǎn)后，依次訪問V1的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問

33、到；要解決的問題:怎樣依次訪問Vi的鄰接點(diǎn)?怎樣依次從它的鄰接點(diǎn)出發(fā),廣度優(yōu)選遍歷圖?我們用到的主要的數(shù)據(jù)構(gòu)造就是隊(duì)列.例142350 1 2 3 4 51fr遍歷序列：10 1 2 3 4 54fr遍歷序列：1 40 1 2 3 4 54 3fr遍歷序列：1 4 30 1 2 3 4 5fr隊(duì)列空結(jié)點(diǎn)在入隊(duì)時(shí)進(jìn)展訪問，f指針指向當(dāng)前擴(kuò)展結(jié)點(diǎn)110 1 2 3 4 54 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2fr遍歷序列：1 4 3 20 1 2 3 4 5 3 2 5fr遍歷序列：1 4 3 2 511 41 40 1 2 3 4 5 2 5fr遍歷序列：1 4 3

34、 2 50 1 2 3 4 5 5fr遍歷序列：1 4 3 2 50 1 2 3 4 5 fr遍歷序列：1 4 3 2 51 4 31 4 3 21 4 3 2 514356782輸入：8 101 41 51 62 6 2 73 53 43 75 75 8編程實(shí)現(xiàn)：輸入以以下圖，按深度優(yōu)先遍歷和廣度優(yōu)先遍歷輸出圖的結(jié)點(diǎn)。圖的dfsconst max=100;var a:array1.max,1.max of integer; f:array1.max of 0.1; /標(biāo)志數(shù)組 n,m,i:integer; procedure init; var i,j,x,y:integer; begin

35、readln(n,m); fillchar(f,sizeof(f),0); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; end;procedure dfs(i:integer);深搜 var j:integer; begin write(i, ); fi:=1; for j:=1 to n do if (fj=0)and(ai,j=1) then dfs(j); end;procedure bfs(i:integer);廣搜 var j,k:integer; begin fillchar(q,sizeof(q),0);

36、f :=0; 隊(duì)首 r :=1; 尾 q1:=i; i進(jìn)隊(duì)列 write(i, ); fi:=1; 標(biāo)志 while f r do 隊(duì)列不空 begin inc(f); k:=qf; 出隊(duì) for j:=1 to n do if (ak,j=1)and(fj=0) then begin write(j, ); fj:=1; inc(r); 進(jìn)隊(duì) qr:=j; end; end; end;BEGINInit; /讀入圖數(shù)據(jù),初始化標(biāo)志數(shù)組For i:=1 to n do if fi = 0 then dfs(i);Writeln;fillchar(f,sizeof(f),0); for i:=1

37、 to n do if fi=0 then bfs(i);END.問題描繪 學(xué)校放暑假時(shí)，信息學(xué)輔導(dǎo)教師有n本書要分給參加培訓(xùn)的n個(gè)學(xué)生。如：A，B，C，D，E共5本書要分給參加培訓(xùn)的張、劉、王、李、孫5位學(xué)生，每人只能選1本。教師事先讓每個(gè)人將自己喜歡的書填寫在如下的表中，然后根據(jù)他們填寫的表來分配書本，希望設(shè)計(jì)一個(gè)程序幫助教師求出可能的分配方案，使每個(gè)學(xué)生都滿意。ABCDE張YY王YY劉YY孫Y李YY5、借書問題輸入格式：第一行一個(gè)數(shù)n學(xué)生的個(gè)數(shù)，書的數(shù)量 以下共n行，每行n個(gè)0或1由空格隔開，第I行數(shù)據(jù)表示第i個(gè)同學(xué)對所有書的喜歡情況。0表示不喜歡該書，1表示喜歡該書。輸出格式：依次輸出

38、每個(gè)學(xué)生分到的書號。樣例：輸入：50 0 1 1 01 1 0 0 00 1 1 0 00 0 0 1 00 1 0 0 1輸出：3 1 2 4 5分析: a:array1.maxn,1.maxnof 0.1; b:array1.maxnof integer; 方案:bi是第i個(gè)人借第bi本書 book:array1.maxnof boolean; booki:能否可以借第i本書, 初始:true,一旦有人借了:就改為:false算法設(shè)計(jì):procedure try(i:integer);搜索第i個(gè)人可以借的書bi var j:integer; begin if i=n+1 then 輸出結(jié)果

39、 else for j:=1 to n do if 第i個(gè)人可以借第j 本書 then begin 記錄下bi; 標(biāo)記第j本數(shù)已被借; try(i+1); 刪除書的被借標(biāo)志; end; end;const maxn=10;var a:array1.maxn,1.maxnof 0.1; b:array1.maxnof integer; book:array1.maxnof boolean; n:integer; procedure init; var i,j:integer; begin assign(input,book.in); reset(input); fillchar(b,sizeof

40、(b),0); fillchar(book,sizeof(book),true); readln(n); for i:=1 to n do for j:=1 to n do read(ai,j); close(input); end; procedure print; var i:integer; begin for i:=1 to n-1 do write(bi, ); writeln(BN); end; procedure try(i:integer); var j:integer; begin if i=n+1 then print; for j:=1 to n do if bookj

41、and (ai,j=1) then begin bi:=j; bookj:=false; try(i+1); bookj:=true; end; end;Begin init; try(1); end.火力中心布局(自習(xí)) 現(xiàn)有一張由n個(gè)堡壘組成的交通圖，任意兩個(gè)堡壘之間只有一條通行道路。為了確保道路暢通，必須在某些堡壘上建立火力中心，每個(gè)火力中心都可以對其相連的所有交通線進(jìn)展全天候的監(jiān)控，防止敵人侵略。如今的問題是如何設(shè)置火力中心的布局，才能用最少的火力中心控制所有交通道路。輸入： 堡壘數(shù)n(1n10000)； 以下每行為i，j，表示堡壘i與堡壘j連接。以0 0標(biāo)志完畢； 輸出： w行，每行

42、為火力中心所在的堡壘號。 火力中心數(shù)w數(shù)學(xué)模型和解題的根本思路 假設(shè)將堡壘設(shè)為頂點(diǎn)、堡壘間的交通線設(shè)為邊的話，那么交通圖為一張無向圖。由于任意兩個(gè)堡壘之間只有一條通行道路，且沒有明確出發(fā)點(diǎn)，因此這張無向圖構(gòu)成了一棵無根樹。所謂支配集是圖的一個(gè)滿足下述條件的頂點(diǎn)子集：即圖的任意頂點(diǎn)或?qū)儆谠摷?，或至少與該集合的一個(gè)頂點(diǎn)相鄰。顯然，火力點(diǎn)就是支配集中的頂點(diǎn)。此題的數(shù)學(xué)模型就是在交通圖對應(yīng)的無根樹中，計(jì)算含頂點(diǎn)數(shù)最少的最小支配集。 假設(shè)是一棵明確了頂點(diǎn)間父子關(guān)系的有根樹的話，我們很容易找到計(jì)算最小支配集的方法： 按照自底而上、由右而左的順序搜索每一條邊。假設(shè)一條邊的兩個(gè)端點(diǎn)為訪問，那么父頂點(diǎn)進(jìn)入支配

43、集，由其支配祖父頂點(diǎn)和所有兒子。依次類推，直至根被訪問為止。 第一步：建立邊表。由于交通圖為一張無向圖，因此我們將每條邊拆分成方向互為相反的兩條邊，即(xi，yi)作為第i條邊存儲(chǔ)，(yi，xi)作為第n+i條邊存儲(chǔ):for i1 to n-1 do建立邊表。由于是無向圖，因此將第i條邊k,j分別存儲(chǔ)于xi,yi和xn+i-1,yn+i-1 begin readln(f,xi,yi);讀第i條邊的兩個(gè)端點(diǎn) xi+n-1yi; yi+n-1xi反向存儲(chǔ)第i條邊的兩個(gè)端點(diǎn) end;for第二步：通過深度優(yōu)先搜索將無根樹轉(zhuǎn)化為明確頂點(diǎn)間父子關(guān)系的有根樹。 首先從頂點(diǎn)1出發(fā)，按照縱深搜索的策略構(gòu)造一棵

44、深度優(yōu)先搜索樹，并記下每個(gè)頂點(diǎn)的父頂點(diǎn)。由于樹邊的父子關(guān)系未明確,因此逐邊搜索。方向是由左而右、由上而下，對于第i個(gè)被訪問的頂點(diǎn)來說，所有訪問順序比i大的頂點(diǎn)，不是該頂點(diǎn)的后代頂點(diǎn)就是位于該頂點(diǎn)的右方樹枝上。例如設(shè)cd表為按照深度優(yōu)先搜索順序存儲(chǔ)的被訪問頂點(diǎn)，即第i個(gè)被訪問的頂點(diǎn)為cdi。在深度優(yōu)先搜索樹中，其父親為ptcdi。我們通過遞歸過程encode計(jì)算深度優(yōu)先搜索的訪問順序表cd和父指針表pt：procedure encode(nw,last:integer);輸入當(dāng)前頂點(diǎn)nw和父頂點(diǎn)last，遞歸計(jì)算cd和pt表var i:integer;begin inc(nm); cdnmnw;

45、nw進(jìn)入深度優(yōu)先搜索的訪問順序表 cvnwtrue;ptnw last; 設(shè)nw已訪問，其父頂點(diǎn)為last for i1 to 2*n-2 do )遞歸訪問與nw相連的未訪問邊，這些邊的另一端點(diǎn)為nw的兒子 if(xi=nw)and not cvyithen encode(yi,nw end;encode第三步：逆推深度優(yōu)先搜索的訪問順序，計(jì)算最小支配集按照深度優(yōu)先搜索的逆向順序，即由右而左、由下而上的順序訪問每個(gè)頂點(diǎn)，依次將每條未訪問邊父子頂點(diǎn)未訪問的父頂點(diǎn)設(shè)為火力點(diǎn),由其控制祖父頂點(diǎn)和所有兒子。例如圖，可在第1、3、5個(gè)被訪問的頂點(diǎn)處布局火力點(diǎn)。主程序建立邊表x和y；fillchar(cv

46、,sizeof(cv),0);nm0;訪問表cv和訪問順序表cd的長度初始化encode(1,1);從頂點(diǎn)1出發(fā)進(jìn)展深度優(yōu)先搜索，計(jì)算訪問順序表cd和父指針表pt fillchar(cv,sizeof(cv),0); w0; 訪問表cv和火力點(diǎn)數(shù)初始化for in downto 2 do按照由右而左、由下而上的順序訪問每個(gè)頂點(diǎn)，依次將每條未訪問邊父子頂點(diǎn)未訪問的父頂點(diǎn)設(shè)為火力點(diǎn) if not cvcdi and not cvptcdi假設(shè)深度優(yōu)先搜索中第i個(gè)被訪問的頂點(diǎn)和其父親當(dāng)前未訪問，那么其父親設(shè)為火力點(diǎn) then begin inc(w);write(ptcdi, );在父端點(diǎn)處增設(shè)一個(gè)

47、火力點(diǎn)，輸出該火力點(diǎn)序號 cvptcditrue置火力點(diǎn)已訪問標(biāo)志 end;then writeln(w);輸出火力點(diǎn)數(shù)任務(wù)A: 題目給出一個(gè)完好道路圖，請編程找出所有必經(jīng)之點(diǎn)。請注意，輸出必經(jīng)之點(diǎn)時(shí)，應(yīng)不包括起點(diǎn)和終點(diǎn)。任務(wù)B: 假定賽跑必須在相鄰的2天來舉行。因此，要把原來給定的完好道路圖分成兩個(gè)子道路圖。第1天從點(diǎn)0出發(fā)，完畢于“分裂點(diǎn)。第2天從“分裂點(diǎn)出發(fā)，完畢于點(diǎn)N。 題目給出一個(gè)完好道路圖C，請編程輸出所有可能的“分裂點(diǎn)任務(wù)B?！胺至腰c(diǎn)S一定不是起點(diǎn)或終點(diǎn)。C可被S分成兩個(gè)完好的子道路：這兩個(gè)子道路沒有公共的箭頭線，并且S是這兩個(gè)子道路的唯一公共點(diǎn)。在上的例子中，僅點(diǎn)3是“分裂點(diǎn)。輸入數(shù)據(jù) 輸入文件INPUTTXT描繪一個(gè)完好道路最多50個(gè)點(diǎn)，最多100個(gè)箭頭，文件共n1行。前面n行0n-1描繪箭頭的終點(diǎn)。第i行中的每一個(gè)數(shù)字表示從點(diǎn)i0in1出發(fā)的每一個(gè)箭頭的終點(diǎn)。以2作為該行的完畢。文件的最后一行第n行中有一個(gè)數(shù)字1，表示文件的完畢。輸出數(shù)據(jù) 你的程序向輸出文件OUTPUTTXT寫入兩行數(shù)據(jù)，第1行表示必經(jīng)點(diǎn)子任務(wù)A首先是必經(jīng)點(diǎn)的總數(shù)，其后是必經(jīng)點(diǎn)的標(biāo)號，標(biāo)號的順序無關(guān)緊要。第2行表示“分裂點(diǎn)：首先是分裂點(diǎn)的總數(shù)，其后是分裂點(diǎn)的標(biāo)號，標(biāo)號出現(xiàn)的先后順序無關(guān)緊要子任務(wù)B。必經(jīng)點(diǎn)和分裂點(diǎn)的特征 必經(jīng)點(diǎn):是指運(yùn)發(fā)動(dòng)從起