夏令營(yíng)基礎(chǔ)班圖及其應(yīng)用

1、圖及其應(yīng)用一、圖的基本概念二、圖的存儲(chǔ)結(jié)構(gòu)三、圖的遍歷四、無(wú)向圖的傳遞閉包五、最短路徑六、最小生成樹七、拓?fù)渑判騼?nèi)容： 圖是由一個(gè)頂點(diǎn)的集合V和一個(gè)頂點(diǎn)間關(guān)系的集合E組成： 記 G=（V，E） V：頂點(diǎn)的有限非空集合。 E：頂點(diǎn)間關(guān)系的有限集合（邊集）。 存在一個(gè)結(jié)點(diǎn)v，可能含有多個(gè)前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。一、 圖的基本概念125341253412534圖2圖3圖1 1、圖的的定義無(wú)向圖： 在圖G=（V，E）中，如果對(duì)于任意的頂點(diǎn)a，bV，當(dāng)(a，b)E時(shí)，必有（b，a）E（即關(guān)系R對(duì)稱），此圖稱為無(wú)向圖。無(wú)向圖中用不帶箭頭的邊表示頂點(diǎn)的關(guān)系 V=1, 2, 3, 4, 5 E=(1, 2),(1

2、, 3),(1, 4),(2,3),(2,5),(3, 5),(4,5) 125342、無(wú)向圖和有向圖有向圖： 如果對(duì)于任意的頂點(diǎn)a，bV，當(dāng)(a，b)E時(shí) ，(b，a)E未必成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)。V=1, 2, 3, 4,5 E= , , , , , 12534在無(wú)向圖中：頂點(diǎn)v的度是指與頂點(diǎn)v相連的邊的數(shù)目D(v)。D(2)=33、頂點(diǎn)的度、入度和出度在有向圖中：入度以該頂點(diǎn)為終點(diǎn)的邊的數(shù)目和 . ID(3)=2 出度以該頂點(diǎn)為起點(diǎn)的邊的數(shù)目和 . OD(3)=1度數(shù)為奇數(shù)的頂點(diǎn)叫做奇點(diǎn)，度數(shù)為偶數(shù)的點(diǎn)叫做偶點(diǎn)。度：等于該頂點(diǎn)的入度與出度

3、之和。 D(5)=ID(5)+OD(5)=1+2=3 1253412534結(jié)論：圖中所有頂點(diǎn)的度=邊數(shù)的兩倍圖1:無(wú)向圖圖2：有向圖無(wú)向完全圖 在圖G=（V，E）中，如果對(duì)于結(jié)點(diǎn)a，b，存在滿足下述條件的結(jié)點(diǎn)序列x1xk(k1) x1=a，xk=b (xi，xi+1)E i=1k-1則稱結(jié)點(diǎn)序列x1=a，x2，xk=b為結(jié)點(diǎn)a到結(jié)點(diǎn)b的一條路徑，而路徑上邊的數(shù)目（k-1）稱為該路徑的長(zhǎng)度。1253412534圖1圖2圖1: 1、(1,2,3,5) 長(zhǎng)度=3 2、(1,2,3,5,2) 長(zhǎng)度=4 3、(1,2,5,4,1) 長(zhǎng)度=4圖2: (1,2,5,4) 長(zhǎng)度=3（1）、如果一條路徑上的結(jié)點(diǎn)

4、除起點(diǎn)x1和終點(diǎn)xk可以相同外，其它結(jié)點(diǎn)均不相同，則稱此路徑為一條簡(jiǎn)單路徑。（2）、x1=xk的簡(jiǎn)單路徑稱為回路（也稱為環(huán)）4、路徑、簡(jiǎn)單路徑、回路5、連通、連通圖、連通分量 (無(wú)向圖)連通：“連成一片”。連通圖：“能連成一片的圖”。1253412534678圖一：連通圖圖二：非連通圖定義：連通：如果存在一條從頂點(diǎn)u到v有路徑，則稱u和v是連通的。連通圖：圖中任意的兩個(gè)頂點(diǎn)u和v都是連通的，稱為連通圖。 否則稱為非連通圖。連通分量：無(wú)向圖中的極大連通子圖。圖二中有3個(gè)連通分量：1 2 4 5 3 6 7 8求連通分量數(shù)，最大連通分量等。有向圖：強(qiáng)連通、強(qiáng)連通圖、強(qiáng)連通分量 6、帶權(quán)圖 圖中的邊

5、可以加上表示某種含義的數(shù)值，數(shù)值稱為邊的權(quán)，此圖稱為帶權(quán)圖。也稱為網(wǎng)。 一般的圖邊上沒(méi)有數(shù)字，邊僅表示兩個(gè)頂點(diǎn)的相連接關(guān)系。12534234213212534二、圖的存儲(chǔ)結(jié)構(gòu)ABDCE12345頂點(diǎn)：數(shù)組或記錄邊：鄰接矩陣/鄰接表 G=( V,E ) 鄰接矩陣是表示結(jié)點(diǎn)間相鄰關(guān)系的矩陣。若G=（V，E）是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，則G的鄰接矩陣是如下定義的二維數(shù)組 a1.n,1.n。ai,j=1 (或權(quán)值)：無(wú)向圖：有邊( i , j )和邊( j , i ) 有向圖：有邊0: i 到 j 無(wú)邊1、圖的鄰接矩陣表示法125340 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 1

6、0 1 1 1 01 2 3 4 51 23451253423421320 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 01 2 3 4 51 2345125340 1 0 1 00 0 1 0 11 0 0 0 00 0 0 0 00 0 1 1 01 2 3 4 51 2345對(duì)角線為0：自身不相連。無(wú)向圖：是對(duì)稱矩陣。有向圖一般不是。第i行非0 的個(gè)數(shù)是結(jié)點(diǎn)i的度具體到題目時(shí)，數(shù)據(jù)的給出格式多種多樣：1）、直接給出鄰接矩陣，直接讀即可。如：輸入文件內(nèi)容：50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0ma

7、xn=100a:array1.maxn,1.maxn of integerfillchar(a,sizeof(a),0);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);1253423421322）、給出邊的頂點(diǎn)。如輸入文件：兩個(gè)頂點(diǎn)及權(quán)值571 2 21 3 21 4 32 3 12 5 33 5 24 5 4125342342132readln(n); readln(m);for k:=1 to m do begin readln(i,j,x); ai,j:=x; aj,i:=x; end62 3 63 4 5 63 1 4 6

8、3 2 3 53 2 4 64 1 2 3 51235463)、給出每個(gè)頂點(diǎn)的鄰接點(diǎn) readln(n); for i:=1 to n do begin read(k); for j:=1 to k do begin read(x); ai,x:=1;ax,i:=1; end; end;125344無(wú)權(quán)圖:設(shè)置結(jié)點(diǎn)指針結(jié)點(diǎn)鄰接點(diǎn)指針2、鄰接表 :1234523413512515234鄰結(jié)點(diǎn)頭結(jié)點(diǎn)type point=node; node=record v:integer; next:point; end;var a:array1.maxvof point;vnext readln(n1,n2)

9、; new(p); p.v:=n2; p.next:=an1; an1:=p; new(p); p.v:=n1; p.next:=an2; an2:=p;125342342132123452232431231531221521354233244頭指針鄰接點(diǎn)指針結(jié)點(diǎn)鄰接點(diǎn)指針鄰接點(diǎn)邊權(quán)值下一個(gè)鄰接點(diǎn)指針有權(quán)圖：type edge = node; node = record v: integer; weight : integer; next : edge; end; vpoint = record v: integer; link : edge; end;var a : array1.maxn

10、of vpoint;vlinkvweightnext鄰接矩陣和鄰接表的優(yōu)缺點(diǎn)：125340 1 1 1 01 0 1 0 11 1 0 0 11 0 0 0 10 1 1 1 01 2 3 4 51 23451234523413512515234鄰結(jié)點(diǎn)頭結(jié)點(diǎn)鄰接表鄰接矩陣鄰接矩陣：代碼書寫簡(jiǎn)單，找鄰接點(diǎn)慢鄰接表：代碼書寫較復(fù)雜，找鄰接點(diǎn)快一般采用鄰接矩陣1763245980 1 0 0 0 0 0 0 01 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 10 0 0 0 0 0 1 0 00 0 0 0 0 1

11、 0 0 00 0 0 0 0 0 0 0 00 0 0 0 1 0 0 0 01234521679鄰結(jié)點(diǎn)頭結(jié)點(diǎn)67895鄰接表鄰接矩陣稀疏圖：邊表type node=record w:integer; /邊權(quán) u,v:integer; /兩個(gè)結(jié)點(diǎn) end;var e: array1.maxn*(maxn-1) div 2 of node; /邊三、圖的遍歷 給出一個(gè)圖G，從某一個(gè)初始點(diǎn)出發(fā)，按照一定的搜索方法對(duì)圖中的每一個(gè)結(jié)點(diǎn)訪問(wèn)僅且訪問(wèn)一次的過(guò)程。 訪問(wèn)結(jié)點(diǎn)：處理結(jié)點(diǎn)的過(guò)程。如輸出、查找結(jié)點(diǎn)的信息。 按照搜索方法的不同，通常有兩種遍歷方法： 1、深度優(yōu)先搜索dfs 2、廣度優(yōu)先搜索bfs

12、1、深度優(yōu)先搜索DFS遍歷算法（遞歸過(guò)程）： 1)從某一初始出發(fā)點(diǎn)i開始訪問(wèn)： 輸出該點(diǎn)編號(hào)；并對(duì)該點(diǎn)作被訪問(wèn)標(biāo)志（以免被重復(fù)訪問(wèn)）。 2)再?gòu)膇的其中一個(gè)未被訪問(wèn)的鄰接點(diǎn)j作為初始點(diǎn)出發(fā)繼續(xù)深搜。 當(dāng)i的所有鄰接點(diǎn)都被訪問(wèn)完，則退回到i的父結(jié)點(diǎn)的另一個(gè)鄰接點(diǎn)k再繼續(xù)深搜。直到全部結(jié)點(diǎn)訪問(wèn)完現(xiàn):a1.maxn,1.maxn:邊的鄰接矩陣。1：有邊；0：無(wú)邊f(xié)1.maxn:boolean 標(biāo)記是否被訪問(wèn)過(guò)。 True: 已訪問(wèn)；flase：沒(méi)訪問(wèn)。初始值：false10121 41 51 64 8 5 34 35 76 27 102 93 77 2Procedure i

13、nit; /初始化 begin readln(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end; end;procedure dfs(k:integer);/從k點(diǎn)出發(fā)遍歷 var j:integer; /局部變量？ begin write(k, ); fk:=true; for j:=1 to n do if (fj=false)and(ak,j=1) then dfs(j); end;上圖的遍歷結(jié)果：Dfs(1)?主程序begin fillchar(f,sizeof(f),false); for

14、 i:=1 to n do if not fi then dfs(i);end;求無(wú)向的連通分量 sum:=0; for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum);125346782、廣度優(yōu)先搜索(寬度優(yōu)先搜索）BFS 按層次遍歷： 從圖中某結(jié)點(diǎn)i出發(fā)，在訪問(wèn)了i之后依次訪問(wèn)i的各個(gè)未曾訪問(wèn)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問(wèn)的結(jié)點(diǎn)都被訪問(wèn)到。1435678291014356782910實(shí)現(xiàn)： 隊(duì)列：q1.maxn f1.n:boolean: 判重he

15、adtailprocedure bfs(i:integer);/ bfs.pas var j,k:integer; begin fillchar(q,sizeof(q),0); head:=0; tail:=1; q1:=i; fi:=true; while headtail do /隊(duì)列非空 begin inc(head); /出隊(duì) k:=qhead; write(k, ); for j:=1 to n do if (ak,j=1)and(fj=false) then begin inc(tail); /進(jìn)隊(duì) qtail:=j; fj:=true; end; end; end;3、圖的遍歷的

16、簡(jiǎn)單應(yīng)用1、犯罪團(tuán)伙【問(wèn)題描述】 警察抓到了n個(gè)罪犯，警察根據(jù)經(jīng)驗(yàn)知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個(gè)團(tuán)伙，但通過(guò)警察的審訊，知道其中的一些罪犯之間相互認(rèn)識(shí)，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識(shí)，有可能一個(gè)犯罪團(tuán)伙只有一個(gè)人。請(qǐng)你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號(hào)從1至n?！据斎搿?第一行：n（1000,罪犯數(shù)量）。 第二行：m（5000，關(guān)系數(shù)量）。 以下m行，每行兩個(gè)數(shù)：i 和j，中間一個(gè)空格隔開，表示罪犯i和罪犯j相互認(rèn)識(shí)?！据敵觥?一個(gè)整數(shù)，犯罪團(tuán)伙的數(shù)量?！緲永斎搿?18 1 24 53 41 35 67 105 108 9【樣例輸出】 3樣例

17、說(shuō)明：共三個(gè)集團(tuán)。把n個(gè)人看成圖的n個(gè)頂點(diǎn)；相互認(rèn)識(shí)的連一無(wú)向條邊。相互認(rèn)識(shí)的所有人構(gòu)成一個(gè)極大連通子圖。問(wèn)題轉(zhuǎn)化為：求無(wú)向圖的連通分量 （有多少個(gè)極大連通子圖）1234106579811 建圖 fillchar(f,sizeof(f),false); /訪問(wèn)標(biāo)志 sum:=0; for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum); 算法：12354672、郵遞員 郵遞員在送信時(shí)，為了節(jié)省路途，自己規(guī)定：每次總是從n個(gè)村子中選擇其中一個(gè)合適的村子出發(fā)，途中每個(gè)村子僅且經(jīng)過(guò)一次，送完所有的信。已知各個(gè)

18、村子的道路連通情況。請(qǐng)你幫郵遞員選擇一條合適的路線。輸入：第一行：整數(shù)n：村子的個(gè)數(shù)。接下來(lái)是一個(gè)n*n的0、1矩陣，表示n個(gè)村子的連同情況，如：ai,j=1 ，表示第i和第j個(gè)村子之間有路可走，如果ai,j=0，表示他們之間無(wú)路可走。輸出：一條可行的路線輸入：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分析： 郵遞員從某一個(gè)村子A出發(fā)；每個(gè)村子訪問(wèn)僅且訪問(wèn)一次，最后到達(dá)村子B結(jié)束，從A到B的路線成為哈密頓路。 如果A和B重

19、合，即回到出發(fā)點(diǎn)，稱為哈密頓回路。b:array1.maxn of integer; /記錄哈密頓路 讀入圖：ai,j for i:= 1 to n do begin fillchar(visited,sizeof(visited),false); b1:=i; visitedi:=true; dfs(i,1); end; print(0); procedure dfs( i, k: integer);/從結(jié)點(diǎn)i開始找，已找到有k個(gè)點(diǎn)，要搜第k+1個(gè)點(diǎn) i是路上的第k個(gè)點(diǎn)。 var j:integer; begin if k=n then print(1);/找到一條路 for j:=1 to

20、 n do if (aj,i=1) and (visitedj=false) then begin visitedj:=true; bk+1:=j;/找到第k+1個(gè)點(diǎn)并記下 dfs(j,k+1); visitedj:=false; /回溯 end; end;怎樣求哈密頓回路？procedure print(k:integer);/輸出 var i:integer; begin if k=0 then writeln(no round) else begin for i:=1 to n-1 do write(bi, ); writeln(bn); end; halt; end;3 、安排座位 n

21、個(gè)客人圍著一個(gè)桌子吃飯，每一個(gè)人都至少認(rèn)識(shí)其他的2個(gè)客人。請(qǐng)?jiān)O(shè)計(jì)程序求得n個(gè)人的一種坐法，使得每個(gè)人都認(rèn)識(shí)他左右的客人。輸入:第一行:n（吃飯人的個(gè)數(shù)）。以下n行：第i行的第一個(gè)數(shù)k表示第i個(gè)人認(rèn)識(shí)的人數(shù)，后面k個(gè)數(shù)依次為i認(rèn)識(shí)的人的編號(hào)。輸出：所有座法，要求第一個(gè)人為1號(hào)作為起點(diǎn)，按順時(shí)針輸出其它人的編號(hào)。樣例輸入：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 3123546構(gòu)造無(wú)向圖，找一條哈密頓回路 readln(n); for i:=1 to n do

22、 begin read(k); for j:=1 to k do begin read(x); ai,x:=1;ax,i:=1; end; end;建圖：procedure dfs(i,k:integer);/從i點(diǎn)開始找點(diǎn)，已有m個(gè)點(diǎn) var j:integer; begin if (k=n)and(ab1,bk=1) then print(1); for j:=1 to n do if (ai,j=1) and (visitedj=0) then begin visitedj:=1; bk+1:=j; dfs(j,k+1); visitedj:=0; end; end;procedure

23、main; begin fillchar(visited,sizeof(visited),0); b1:=1; visited1:=1; dfs(1,1); print(0); end;4、素?cái)?shù)鏈設(shè)計(jì)程序?qū)?。n（20）排成一排，使任意兩個(gè)相鄰的數(shù)的和為素?cái)?shù)。第1個(gè)和最后一個(gè)的和也為素?cái)?shù).輸出:第一個(gè)數(shù)為1.如：樣例輸入：6樣例輸出：1 4 3 2 5 6主程序 fillchar(visited,sizeof(visited),0); b1:=1; visited1:=1; dfs(1,1);b1.maxn:記錄結(jié)果序列。Visited1.maxn: 標(biāo)記是否已用過(guò)搜索過(guò)程 procedure

24、 dfs(i,k:integer); /已找到第k個(gè)數(shù)是i，找第k+1個(gè) var j:integer; begin if (n=k)and(check(b1+bk) then print(1); for j:=1 to n do if (visitedj=0) and (check(i+j) then begin visitedj:=1; bk+1:=j; dfs(j,k+1); visitedj:=0; end; end;判讀素?cái)?shù)function check(i:integer):boolean; var j:integer; begin for j:=2 to i-1 do if i mo

25、d j=0 then exit(false); exit(true); end;優(yōu)化：建立素?cái)?shù)表maxnPrime3.2*maxn-1: boolean素?cái)?shù)：true；非素?cái)?shù)：false篩選法建立素?cái)?shù)表篩選法求素?cái)?shù) for i:=1 to n do primei:=true; prime1:=false; for i:=2 to trunc(sqrt(n) do if primei then begin j:=2*i; while j=n do begin primej:=false; j:=j+i; end; end;四、圖的傳遞閉包G=( V, E )問(wèn)題：頂點(diǎn) i到j(luò)是否存在一條從i到j(luò)

26、的路徑？G的傳遞閉包： G*=（V，E*）E*=（i，j）：圖G中存在一條i到j(luò)的路徑判斷無(wú)向圖的連通性12346571 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 鄰接矩陣G*G傳遞閉包的算法：ijk1、結(jié)點(diǎn) i 到 j 有邊則有路徑。2、 i 到 j

27、之間沒(méi)有邊： 如果存在另外的一個(gè)結(jié)點(diǎn)k，滿足：i到k有路徑，k到j(luò)有路徑，則i到j(luò)有路徑。否則i到j(luò)沒(méi)有路徑。can i , j =true:i到j(luò)有邊； can i , j = false:無(wú)邊。則：can i , j =can i , j or ( can i , k and can k , j )判斷結(jié)點(diǎn) i 到 j是否有路徑fillchar(f,sizeof(f),false);for i:=1 to n do fi,i:=true; for k:=1 to n do for i:=1 to n do for j:=1 to n do cani,j:=cani,j or (cani,k

28、 and cank,j);過(guò)程：產(chǎn)生數(shù)(noip2001)【問(wèn)題描述:】給出一個(gè)正整數(shù) n（n1050) 和 k 個(gè)變換規(guī)則（k 5 3 6上面的整數(shù) 234 經(jīng)過(guò)變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）:234 534 264 564 共 4 種不同的產(chǎn)生數(shù)。【任務(wù)：】給出一個(gè)整數(shù) n 和 k 個(gè)變換規(guī)則。求經(jīng)過(guò)任意次的變換（0次或多次），能產(chǎn)生出多少個(gè)不同整數(shù)。僅要求輸出個(gè)數(shù)。 【輸入：】第一行：n。第二行：k。以下k行：每行兩個(gè)一位數(shù)：x y，中間一個(gè)空格，表示一個(gè)變換規(guī)則：x可以變?yōu)閥。【輸出：】一個(gè)整數(shù)（滿足條件的個(gè)數(shù)）： 【輸入樣例：】234 22 53 6【樣例輸出：】4應(yīng)用舉例分析

29、：本題搜索顯然是不行的。對(duì)于只需計(jì)數(shù)而不需求具體方案的題目，一般都不會(huì)用搜索解決。 234 72 52 85 75 17 93 64 32579184362: 63: 24: 36*2*3=36乘法原理直接進(jìn)行計(jì)數(shù)。 用fi表示數(shù)字i包括本身可以變成的數(shù)字總個(gè)數(shù) 這里的變成可以是直接變成也可以是間接變成： 比如 3-5, 5-7,那么 3-7那么對(duì)于一個(gè)數(shù)a（用數(shù)組存,長(zhǎng)度為n），根據(jù)乘法原理它能產(chǎn)生出不同整數(shù)數(shù)量：fa1*fa2*fa3*fan 求fi:i能變成其它數(shù)字的個(gè)數(shù)？構(gòu)造09十個(gè)點(diǎn)的圖i能到達(dá)哪些點(diǎn)？/noip2001const maxn=51;var a:array0.9,0.9

30、 of boolean; f:array0.9 of integer; ans:array0.500 of shortint; s:string; n,len:integer;procedure init; var k,i,p,q:integer; begin fillchar(a,sizeof(a),false); for i:=0 to 9 do ai,i:=true; readln(s); readln(k); for i:=1 to k do begin readln(p,q); ap,q:=true; end; end;構(gòu)圖生產(chǎn)數(shù)組fprocedure makef; var i,j,

31、k:integer; begin for k:=0 to 9 do for i:=0 to 9 do for j:=0 to 9 do ai,j:=ai,jor(ai,k and ak,j); for i:=0 to 9 do for j:=0 to 9 do if ai,j then inc(fi); end;procedure mul(k:integer); /高精度乘單精度 var i,m:integer; begin len:=ans0; for i:=1 to len do ansi:=ansi*k; for i:=1 to len do begin ansi+1:=ansi+1+a

32、nsi div 10; ansi:=ansi mod 10; end; m:=anslen+1; while m0 do begin inc(len); anslen:=m mod 10; m:=m div 10; end; ans0:=len; end;mainprocedure main; var i,k:integer; begin makef; n:=length(s); fillchar(ans,sizeof(ans),0); ans1:=1; ans0:=1; for i:=1 to n do begin k:=ford(si)-48; if k0 then mul(k); end

33、; end; procedure print; var i:integer; begin for i:=ans0 downto 1 do write(ansi); writeln; end;begin init; main; print;end.引例：現(xiàn)在，我們想從城市A到達(dá)城市E。怎樣走才能使得路徑最短，最短路徑的長(zhǎng)度是多少？ 1234567891011531638438556343五、圖的最短路徑已知各個(gè)城市之間的道路情況如下：圖中兩點(diǎn)間的最短距離兩類問(wèn)題：1、圖中每對(duì)頂點(diǎn)（任意兩點(diǎn)）之間的最短路徑 （弗洛伊德算法：f loyed）。2、圖中一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑 （迪杰斯特拉算法：

34、dijkstra）。一）、計(jì)算每一對(duì)頂點(diǎn)間的最短路徑（floyd算法）目標(biāo)：把圖中任意兩點(diǎn)i與j之間的最短距離都求出來(lái) di,j。原理：根據(jù)圖的傳遞閉包思想：ijkif di,k+dk,jdi,j then di,j=di,k+dk,jfor k:=1 to n do for i:=1 to n do for j:=1 to n do if di,k+dk,jdi,j then di,j:=di,k+dk,j;算法寫法：floyed2.pas初始化條件：D i, i =0 /自己到自己為0；對(duì)角線為0；Di,j=邊權(quán)，i與j有直接相連的邊Di,j= + ，i與j無(wú)直接相連的邊。 / 一般設(shè)為：

35、 maxint/2 or maxlongint/2;舉例： 已知下圖中給定的關(guān)系，求出圖中任意給定兩點(diǎn)之間的最短距離123452317549137輸入：51 51 2 231 3 171 5 492 3 52 4 134 5 7要求：輸出最短距離d1,5。 / floyed2.pas分析：Di,j:表示頂點(diǎn)i到頂點(diǎn)j之間的最短距離。初始化如下：0 23 17 49 23 0 5 13 17 5 0 13 0 749 7 01234523175491370 22 17 35 42 22 0 5 13 20 17 5 0 18 25 35 13 18 0 7 42 20 25 7 0 floyed

36、procedure init; readln(n); readln(p,q); for i:=1 to n do for j:=1 to n do if i=j then di,j:=0 else di,j:=maxint div 2; while not seekeof do begin readln(i,j,w); di,j:=w; dj,i:=w; end;procedure floyed; begin for k:=1 to n do for i:=1 to n do for j:=1 to n do if di,k+dk,j2: 22: 1 3 2 1-3: 17: 1 3 1-4:

37、 35: 1 3 2 4 1-5: 42: 1 3 2 4 5 2-3: 5: 2 3 2-4: 13: 2 4 2-5: 20: 2 4 5 3-4: 18: 3 2 4 3-5: 25: 3 2 4 5 4-5: 7: 4 5 方法一：floyed3.pas設(shè) pathi,j 記錄i到j(luò)的最短路徑中j的前驅(qū)頂點(diǎn)。如樣例：1-4: 35: 1 3 2 4 path1,4=2path1,2=3path1,3=1初始化：i到j(luò)有邊，則 pathi,j:=i; pathj,i :=j for k:=1 to n do for i:=1 to n do for j:=1 to n do if di,

38、k+dk,j0 then begin dfs(i,pathi,j); write(j, ); end; end;iPathi,jj方法二：floyed4.pas設(shè) pathi,j 記錄能使i到j(luò)的距離變短的結(jié)點(diǎn)。初始化：pathi,j= -1: i與j不通的pathi,j:=0; 從i到j(luò)的最短路徑是直接到達(dá)的。開始有邊的都直接到達(dá)。Pathi,j0;從i到j(luò)的最短路徑要經(jīng)過(guò)點(diǎn)pathi,j.for k:=1 to n do for i:=1 to n do for j:=1 to n do if di,k+dk,j0 then begin dfs(i,pathi,j); write(path

39、i,j, ); dfs(pathi,j,j); end; end;輸出i到j(luò)的最短路徑：Write(i); dfs(i,j); write(j);在無(wú)向圖中： 求A到B中間經(jīng)過(guò)的最少結(jié)點(diǎn)？方法：邊權(quán)值設(shè)為1，求A到B的最短距離d。d-1是中間經(jīng)過(guò)的最少結(jié)點(diǎn)。二）、計(jì)算某一頂點(diǎn)到其它所有頂點(diǎn)的最短路徑 （單源最短路徑問(wèn)題：dijkstra 算法）開始點(diǎn)（源點(diǎn)）：startDi:頂點(diǎn)i到start的最短距離。初始：Dstart=0；Di=astart,i （無(wú)邊設(shè)為maxint）1253410757173449start其它n-1個(gè)點(diǎn)集合1：已求點(diǎn)集合2：未求點(diǎn)1、在集合2中找一個(gè)到start距離

40、最近的頂點(diǎn)k ，距離=dk2、把頂點(diǎn)k加到集合1中，同時(shí)修改集合2 中的剩余頂點(diǎn)j的dj是否經(jīng)過(guò)k后變短。如果變短修改djIf dk+ak,jdj then dj=dk+ak,j3、重復(fù)1，直至集合2空為止。125341075717344913頂點(diǎn)12345FiTFFFFDi010497Pathi11,21,31,5頂點(diǎn)12345FiTFFFTDi01049207Pathi11,21,31,5,41,5頂點(diǎn)12345FiTTFFTDi01027177Pathi11,21,2,31, 2,41,5511 2 101 5 72 3 172 4 72 5 53 4 344 5 13頂點(diǎn)12345Fi

41、TTTTTDi01027177Pathi11,21,2,31, 2,41,5頂點(diǎn)12345FiTTFTTDi01027177Pathi11,21,2,31, 2,41,5 for i:=1 to n do begin di:=astard,i; fi:=false; end; fstart:=true; / 加入集合1 for i:=2 to n do begin min:=maxlongint; k:=0; for j:=1 to n do if (not fj) and (djmin) then begin min:=dj; k:=j; end; if (k=mb) then exit;

42、/找到目標(biāo) if (k=0)or(min= maxlongint) then exit; /更新結(jié)點(diǎn)求完了 fk:=true; / 加入集合1 for j:=1 to n do /修改集合2中的dj if (not fj) and (dk+ak,jdj) then dj:=dk+ak,j; end;dijkstra 算法Writeln(dstrat,mb) 時(shí)間：O(n2)怎樣輸出路徑？ for i:=1 to n do begin di:=as,i; pathi:=s; end; ds:=0; fs:=true;paths:=0; for i:=2 to n do begin min:=ma

43、xint; k:=0; for j:=1 to n do /找距起點(diǎn)s最近的點(diǎn)k if (not fj) and (djmin) then begin min:=dj; k:=j; end; if (k=t)or(min=maxint) then break; fk:=true; for j:=1 to n do / 更新其他接點(diǎn)的dj if (not fj)and(dk+ak,jdj) then begin dj:=dk+ak,j; pathj:=k;end; end; m:=0; i:=t; while i0 do begin inc(m); waym:=i; i:=pathi; end;

44、 for i:=m downto 1 do write(wayi, );S：起點(diǎn)；t：終點(diǎn)；pathi：i的前驅(qū)結(jié)點(diǎn)；way：從s到t的結(jié)點(diǎn)路徑使用條件：Floyed: 可以有負(fù)權(quán)，無(wú)負(fù)權(quán)回路。O(n3)Dijkstra: 不能有負(fù)權(quán)。O(n2)21534424-7421534424-34圖 1圖 2單源最短路徑的Bellman-ford算法執(zhí)行v-1次，每次對(duì)每條邊進(jìn)行松弛操作時(shí)間O（v*e） v:頂點(diǎn)；e：邊swuvif disu+wdisv then disv:=disu+w;能判斷有無(wú)負(fù)權(quán)回路type edge=record a,b,w :integer; end;var edges

45、:array1.maxeof edge; /邊 dis :array1.maxnof integer; /距源點(diǎn)s距離 pre :array1.maxnof integer; /前驅(qū) e,n,s :integer;求最短路并判是否有負(fù)權(quán)回路function bellman_ford:boolean;var i,j :integer;begin for i:=1 to n-1 do for j:=1 to e do /每條邊松弛 with edgesj do relax(a,b,w); for i:=1 to e do/如果還能松弛，說(shuō)明有負(fù)權(quán)的回路。 with edgesi do if dis

46、a+wdisb then exit(false); exit(true)end;松弛操作procedure relax(u,v,w:integer);begin if disu+w0)and(distx+ax,idisti) then begin disti:=distx+ax,i; if not(vi) then begin t:=(t+1)mod n; qt:=i; vi:=true; end; end; end;SPFA在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個(gè)點(diǎn)出了隊(duì)列就不可能重新進(jìn)入隊(duì)列，但是SPFA中一個(gè)點(diǎn)可能在出隊(duì)列之后再次被放入隊(duì)列，也就是一個(gè)點(diǎn)改進(jìn)過(guò)其它的點(diǎn)之

47、后，過(guò)了一段時(shí)間可能本身會(huì)再次被改進(jìn)，于是再次用來(lái)改進(jìn)其它的點(diǎn)，這樣反復(fù)迭代下去。1、主席的居住城市distp.pas/dist.in/dist.out【問(wèn)題描述】 OI國(guó)共有n個(gè)城市，任意兩個(gè)城市都直接或間接連通，每?jī)蓚€(gè)直接相連的城市之間都有一雙向公路。OI 國(guó)的CHEN主席要選擇其中一個(gè)城市居住，由于他到每個(gè)城市考察的概率是相等的，所以他選擇的城市到 其它所有城市的的最短距離 的和應(yīng)該最小?，F(xiàn)在，給出城市間的道路，請(qǐng)幫助CHEN主席確定居住的城市。【輸入】nn*n的矩陣， ( i , j ) 表示 i到j(luò)之間的距離 ( i , j ) = ( j , i ) ( i , j ) = -1

48、表示 i , j 之間沒(méi)有直接道路?！据敵觥砍鞘芯幪?hào) （如果有多個(gè)城市同時(shí)最小，輸出編號(hào)最小的城市） 最小距離和【輸入樣例】 5-1 31 -1 72 -1 31 -1 30 -1 70 -1 30 -1 76 -1 72 -1 76 -1 40 -1 70 -1 40 -1 【輸出樣例】2234說(shuō)明：數(shù)據(jù)規(guī)模： n=100 ( i , j) =100分析：求出任意兩點(diǎn)間的最短距離。枚舉每一個(gè)頂點(diǎn)到其他n-1個(gè)點(diǎn)的最短距離和。最小者即所求目標(biāo)。2、最優(yōu)乘車（noi97）Travel.pas/traver.in/travel.out【問(wèn)題描述：】 H城是一個(gè)旅游勝地，每年都有成千上萬(wàn)的人前來(lái)觀光

49、。為方便游客，巴士公司在各個(gè)旅游景點(diǎn)及賓館，飯店等地都設(shè)置了巴士站并開通了一些單程巴士線路。每條單程巴士線路從某個(gè)巴士站出發(fā)，依次途經(jīng)若干個(gè)巴士站，最終到達(dá)終點(diǎn)巴士站。 一名旅客最近到H城旅游，他很想去S公園游玩，但如果從他所在的飯店沒(méi)有一路巴士可以直接到達(dá)S公園，則他可能要先乘某一路巴士坐幾站，再下來(lái)?yè)Q乘同一站臺(tái)的另一路巴士, 這樣換乘幾次后到達(dá)S公園。 現(xiàn)在用整數(shù)1,2,N 給H城的所有的巴士站編號(hào)，約定這名旅客所在飯店的巴士站編號(hào)為1S公園巴士站的編號(hào)為N。 寫一個(gè)程序，幫助這名旅客尋找一個(gè)最優(yōu)乘車方案,使他在從飯店乘車到S公園的過(guò)程中換車的次數(shù)最少。【輸入：】第一行有兩個(gè)數(shù)字M和N(1

50、=M=100 1N=500），表示開通了M條單程巴士線路，總共有N個(gè)車站。從第二行到第M+1行依次給出了第1條到第M條巴士線路的信息。其中第i+1行給出的是第i條巴士線路的信息，從左至右按運(yùn)行順序依次給出了該線路上的所有站號(hào)相鄰兩個(gè)站號(hào)之間用一個(gè)空格隔開?！据敵?】 一行。如果無(wú)法乘巴士從飯店到達(dá)S公園，則輸出N0，否則輸出你的程序所找到的最少換車次數(shù)，換車次數(shù)為0表示不需換車即可到達(dá)【樣例輸入：】3 76 74 7 3 62 1 3 5【樣例輸出：】21235467飯店 公園 【樣例輸入：】3 76 74 7 3 62 1 3 51235467飯店 公園 【樣例輸入：】3 76 74 7 3

51、 62 1 3 5構(gòu)造權(quán)為1的有向圖最少換車次數(shù) :d1,n-1六、圖的最小生成樹普里姆算法（prim）克魯斯卡爾（kruskal）網(wǎng)絡(luò)建設(shè)Net.pas/net.in/net.out【問(wèn)題描述：】OI國(guó)由n個(gè)城市組成，所有城市位于一平面坐標(biāo)系中，每個(gè)城市的坐標(biāo)是已知的，且坐標(biāo)都是整數(shù)?，F(xiàn)在，OI國(guó)的CHEN主席想加快網(wǎng)絡(luò)信息傳遞，決定選若干對(duì)城市，每對(duì)城市之間用一條高速網(wǎng)線相連，并且使所有的城市都可以直接或間接相連。已知兩城市之間的距離為它們的直線距離，求所需網(wǎng)線的最小長(zhǎng)度?！据斎耄骸縩n行，每行有兩個(gè)整數(shù)x , y 表示第i個(gè)城市的坐標(biāo)為 (x , y )【輸出：】最短的網(wǎng)線的長(zhǎng)度。 結(jié)果

52、保留3為小數(shù)。【輸入樣例：】62 14 15 43 53 32 3【輸出樣例：】9.236數(shù)據(jù)規(guī)模 n=500 1= x, y =10000 1 2 3 4 5 621345612435173010247235最小生成樹： 含有n個(gè)結(jié)點(diǎn)的圖，從中選n-1條邊，保持n-1個(gè)點(diǎn)中任意兩點(diǎn)是連通的，并且n-1條邊的和最小。這n個(gè)點(diǎn)和這n-1條邊就成為原圖的最小生成樹。任意結(jié)點(diǎn)開始（不妨設(shè)為v1）構(gòu)造最小生成樹：首先把這個(gè)結(jié)點(diǎn)包括進(jìn)生成樹里，然后在那些其一個(gè)端點(diǎn)已在生成樹里、另一端點(diǎn)還未在生成樹里的所有邊中找出權(quán)最小的一條邊，并把這條邊、包括不在生成樹的另一端點(diǎn)包括進(jìn)生成樹，。依次類推，直至將所有結(jié)點(diǎn)

53、都包括進(jìn)生成樹為止。 普里姆算法（prim）1243517301024723512345 for i:=1 to n do begin di:=a1,i; fi:=false; end; f1:=true; /放在生成樹中 ans:=0; for i:=2 to n do begin min:=maxint; for j:=1 to n do if (not fj) and (djmin) then begin min:=dj; k:=j; end; inc(ans,dk); fk:=true; for j:=1 to n do if (not fj) and(ak,jdj) then dj:

54、=ak,j;/修改d end;Prim算法描述：/ai，j：i到j(luò)的邊長(zhǎng)。/Di：結(jié)點(diǎn)i到生成樹中結(jié)點(diǎn)的最短距離/fi:true:在生成樹種，false：不在生成樹中。輸出最小生成樹的邊：pre:array1.maxn of integer; prei:點(diǎn)i的前驅(qū)點(diǎn)tree:array1.maxn-1,1.2 of integer; 記錄邊 for i:=1 to n do begin di:=a1,i; prei:=1; fi:=false; end; /先放1 f1:=true; ans:=0; for i:=1 to n-1 do begin min:=maxint; for j:=1 to n do if (not fj) and (djmin) then begin min:=dj; k:=j; end; treei,1:=k; treei,2:=prek; inc(ans,dk); fk:=true; for j:=1 to n d