第15講：圖及其應(yīng)用

1、第第15講講: 數(shù)據(jù)結(jié)構(gòu)之?dāng)?shù)據(jù)結(jié)構(gòu)之 圖圖一、一、 圖的基本概念圖的基本概念二、圖的存儲結(jié)構(gòu)二、圖的存儲結(jié)構(gòu)三、圖的遍歷三、圖的遍歷四、無向圖的傳遞閉包四、無向圖的傳遞閉包五、最短五、最短 路徑路徑六、最小生成樹六、最小生成樹七、拓?fù)渑判蚱?、拓?fù)渑判?1、圖的的定義、圖的的定義 圖是由頂點圖是由頂點v v的集合和邊的集合和邊e e的集合組成的二元組：的集合組成的二元組： 記記g=g=（v v，e e） 存在一個結(jié)點存在一個結(jié)點v v，可能含有多個前驅(qū)結(jié)點和后繼結(jié)點。，可能含有多個前驅(qū)結(jié)點和后繼結(jié)點。一、一、 圖的基本概念圖的基本概念1253412534無向圖：無向圖： 在圖在圖g=g=（v v

2、，e e）中，如果對于任意的頂點）中，如果對于任意的頂點a a，bvbv，當(dāng)當(dāng)(a(a，b)eb)e時，必有（時，必有（b b，a a）ee（即關(guān)系（即關(guān)系r r對稱），此圖稱為對稱），此圖稱為無向圖。無向圖。無向圖中用不帶箭頭的邊表示頂點的關(guān)系無向圖中用不帶箭頭的邊表示頂點的關(guān)系 v=1, 2, 3, 4, 5 e=(1, 2),(1, 3),(1, 4),(2,3),(2,5),(3, 5),(4,5) 125342、無向圖和有向圖、無向圖和有向圖有向圖：有向圖： 如果對于任意的頂點如果對于任意的頂點a a，bvbv，當(dāng)，當(dāng)(a (a，b)eb)e時時 ，(b(b，a)ea)e未未必成立，

3、則稱此圖為有向圖。必成立，則稱此圖為有向圖。在有向圖中，通常用帶箭頭的邊連接兩個有關(guān)聯(lián)的結(jié)點。在有向圖中，通常用帶箭頭的邊連接兩個有關(guān)聯(lián)的結(jié)點。v=1, 2, 3, 4,5 v=1, 2, 3, 4,5 e= , , , , , e= , , , , , 12534在無向圖中：頂點在無向圖中：頂點v v的度是指與頂點的度是指與頂點v v相連的邊的數(shù)目。相連的邊的數(shù)目。d( 2 )=3d( 2 )=33 3、頂點的度、入度和出度、頂點的度、入度和出度在有向圖中：在有向圖中：入度入度以該頂點為終點的邊的數(shù)目和以該頂點為終點的邊的數(shù)目和 . id(3)=2 . id(3)=2 出度出度以該頂點為起點

4、的邊的數(shù)目和以該頂點為起點的邊的數(shù)目和 . od(3)=1. od(3)=1 度數(shù)為奇數(shù)的頂點叫做奇點，度數(shù)為偶數(shù)的點叫做偶點。度數(shù)為奇數(shù)的頂點叫做奇點，度數(shù)為偶數(shù)的點叫做偶點。度：等于該頂點的入度與出度之和。度：等于該頂點的入度與出度之和。 d(5)=id(5)+od(5)=1+2=3d(5)=id(5)+od(5)=1+2=3 1253412534圖中所有頂點的度圖中所有頂點的度=邊的兩倍邊的兩倍1( )2*niid ve圖1圖2*(1)2nne完全圖完全圖4 4、 路徑、路徑、簡單路徑、回路簡單路徑、回路 在圖在圖g=g=（v v，e e）中，如果對于結(jié)點）中，如果對于結(jié)點a a，b b

5、，存在滿足下述條件的結(jié)點序，存在滿足下述條件的結(jié)點序列列x x1 1xxk k(k (k1)1) x x1 1=a=a，x xk k=b =b (x (xi i，x xi+1i+1)e i=1)e i=1k-1k-1則稱結(jié)點序列則稱結(jié)點序列x x1 1=a=a，x x2 2，x xk k=b=b為結(jié)點為結(jié)點a a到結(jié)點到結(jié)點b b的一條路徑，而路徑上邊的一條路徑，而路徑上邊的數(shù)目（的數(shù)目（k-1k-1）稱為該路徑的長度。）稱為該路徑的長度。1253412534圖1圖2圖圖1: 1、(1,2,3,5) 長度長度=3 2、(1,2,3,5,2) 長度長度=4 3、(1,2,5,4,1) 長度長度=

6、4圖圖2: (1,2,5,4) 長度長度=3（1）、如果一條路徑上的結(jié)點除起點）、如果一條路徑上的結(jié)點除起點x1和終點和終點xk可以相同外，其它結(jié)可以相同外，其它結(jié)點均不相同，則稱此路徑為一條簡單路徑。點均不相同，則稱此路徑為一條簡單路徑。（2）、）、x1=xk的簡單路徑稱為回路（也稱為環(huán)）的簡單路徑稱為回路（也稱為環(huán)）5、連通、連通圖、連通分量、連通、連通圖、連通分量 (無向圖無向圖)直觀理解：直觀理解：連通：連通：“連成一片連成一片”。連通圖：連通圖：“能連成一片的圖能連成一片的圖”。1253412534678圖一圖一圖二圖二確切定義：確切定義：連通連通：如果從頂點：如果從頂點u u到到v

7、 v有路徑，則稱有路徑，則稱u u和和v v是連通的。是連通的。連通圖連通圖：圖中任意的兩個頂點：圖中任意的兩個頂點u u和和v v都是連通的。都是連通的。圖一是連通圖，圖二是非連通圖圖一是連通圖，圖二是非連通圖連通分量：無向圖中的連通分量：無向圖中的極大連通子圖極大連通子圖。圖二中有圖二中有3 3個連通分量：個連通分量：1 2 4 5 3 6 7 81 2 4 5 3 6 7 8求連通分量數(shù)，最大連通分量等。求連通分量數(shù)，最大連通分量等。有向圖：強連通、強連通圖、強連通分量有向圖：強連通、強連通圖、強連通分量 6、帶權(quán)圖、帶權(quán)圖 圖中的邊可以加上表示某種含圖中的邊可以加上表示某種含義的數(shù)值，

8、數(shù)值稱為邊的權(quán)，此圖義的數(shù)值，數(shù)值稱為邊的權(quán)，此圖稱為帶權(quán)圖。也稱為網(wǎng)。稱為帶權(quán)圖。也稱為網(wǎng)。 一般的圖邊上沒有數(shù)字，邊僅表示一般的圖邊上沒有數(shù)字，邊僅表示兩個頂點的相連接關(guān)系。兩個頂點的相連接關(guān)系。125342342132二、圖的存儲結(jié)構(gòu)二、圖的存儲結(jié)構(gòu)1 1、鄰接矩陣（靜態(tài)數(shù)組）、鄰接矩陣（靜態(tài)數(shù)組）2 2、鄰接表（指針數(shù)組）、鄰接表（指針數(shù)組）3 3、邊集數(shù)組、邊集數(shù)組4 4、十字鏈表、十字鏈表5 5、鄰接多重表、鄰接多重表圖的鄰接矩陣表示法圖的鄰接矩陣表示法 鄰接矩陣是表示結(jié)點間相鄰關(guān)系的矩陣。若鄰接矩陣是表示結(jié)點間相鄰關(guān)系的矩陣。若g=g=（v v，e e）是一個具有是一個具有n n

9、個結(jié)點的圖，則個結(jié)點的圖，則g g的鄰接矩陣是如下定義的二維的鄰接矩陣是如下定義的二維數(shù)組數(shù)組a a。1、鄰接矩陣、鄰接矩陣ai,j=1(或權(quán)值或權(quán)值)：無向圖：有邊：無向圖：有邊( i , j )和邊和邊( j , i ) 有向圖：有邊有向圖：有邊0: i 到到 j 無邊無邊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 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

10、 0 0 0 00 0 0 0 00 0 1 1 01 2 3 4 51 2345對角線為對角線為0：自身不相連。：自身不相連。無向圖：是對稱矩陣。有向圖一般不是。無向圖：是對稱矩陣。有向圖一般不是。第第i行非行非0 的個數(shù)是結(jié)點的個數(shù)是結(jié)點i的度的度具體到題目時，數(shù)據(jù)的給出格式多種多樣：具體到題目時，數(shù)據(jù)的給出格式多種多樣：1）、直接給出鄰接矩陣，直接讀即可。）、直接給出鄰接矩陣，直接讀即可。如：如：輸入文件內(nèi)容：輸入文件內(nèi)容：50 2 2 3 02 0 1 0 32 1 0 0 23 0 0 0 40 3 2 4 0maxn=100a:array1.maxn,1.maxn of integ

11、erfillchar(a,sizeof(a),0);readln(n);for i:=1 to n do for j:=1 to n do read(ai,j);1253423421322）、給出邊的頂點。）、給出邊的頂點。如輸入文件：兩個頂點及權(quá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; end2、鄰接表、鄰接表 :方法方法112534234213212345

12、2232431231531221521354233244頭指針頭指針鄰接點指針鄰接點指針結(jié)點鄰接點指針鄰接點邊權(quán)值下一個鄰接點指針type edge = node; node = record data : integer; weight : integer; next : edge; end; vpoint = record data : integer; link : edge; end;var a : array1.maxn of vpoint;/ 具體操作：具體操作：dfs2.pasdatalinkdataweightnext鄰接表方法鄰接表方法2：123452341351251523

13、4125342342132權(quán)值單獨用另外的數(shù)組權(quán)值單獨用另外的數(shù)組w設(shè)置結(jié)點指針設(shè)置結(jié)點指針結(jié)點鄰接點指針type point=node; node=record data:integer; next:point; end;var a:array1.maxvof point;/具體操作：具體操作：dfs3.pasdatanext三、圖的遍歷三、圖的遍歷 給出一個圖給出一個圖g g，從某一個初始點出發(fā)，按照一定的搜索方法對圖，從某一個初始點出發(fā)，按照一定的搜索方法對圖中的每一個結(jié)點訪問僅且訪問一次的過程。中的每一個結(jié)點訪問僅且訪問一次的過程。 訪問結(jié)點：處理結(jié)點的過程。如輸出結(jié)點的信息、求和等，

14、訪問結(jié)點：處理結(jié)點的過程。如輸出結(jié)點的信息、求和等，根據(jù)題目要求。根據(jù)題目要求。 按照搜索方案的不同，通常有兩種遍歷方法：按照搜索方案的不同，通常有兩種遍歷方法： 深度優(yōu)先搜索深度優(yōu)先搜索dfsdfs 廣度優(yōu)先搜索廣度優(yōu)先搜索bfsbfs 1 1、深度優(yōu)先搜索、深度優(yōu)先搜索dfsdfs遍歷算法（遞歸過程）：遍歷算法（遞歸過程）： 1)1)從某一初始出發(fā)點從某一初始出發(fā)點i i開始訪問：開始訪問： 輸出該點編號；并對該點作輸出該點編號；并對該點作被訪問標(biāo)志（以免被重復(fù)訪問）。被訪問標(biāo)志（以免被重復(fù)訪問）。 2) 2)再從再從i i的其中一個未被訪問的鄰接點的其中一個未被訪問的鄰接點j j作為初始

15、點出發(fā)繼續(xù)作為初始點出發(fā)繼續(xù)深搜。深搜。當(dāng)當(dāng)i i的所有鄰接點都被訪問完，則退回到的所有鄰接點都被訪問完，則退回到i i的父結(jié)點的另一個鄰的父結(jié)點的另一個鄰接點接點k k再繼續(xù)深搜。再繼續(xù)深搜。直到全部接點訪問完畢直到全部接點訪問完rocedure dfs(k:integer);/從從k點出發(fā)遍歷點出發(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;/讀入邊的關(guān)系讀入邊的關(guān)系readl

16、n(n); readln(m); for i:=1 to m do begin readln(x,y); ax,y:=1; ay,x:=1; end;上圖的遍歷結(jié)果：上圖的遍歷結(jié)果：dfs(1)? procedure main; var i:integer; begin fillchar(f,sizeof(f),false); for i:=1 to n do if not fi then dfs(i); end;2 2、廣度優(yōu)先搜索、廣度優(yōu)先搜索( (寬度優(yōu)先搜索）寬度優(yōu)先搜索）bfsbfs 廣度優(yōu)先搜索廣度優(yōu)先搜索按層次按層次遍歷的過程，其搜索過程如下：遍歷的過程，其搜索過程如下： 假設(shè)從

17、圖中某結(jié)點假設(shè)從圖中某結(jié)點i i出發(fā)，在訪問了出發(fā)，在訪問了i i之后依次訪問之后依次訪問i i的各個未曾的各個未曾訪問的鄰接點，然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索的順訪問的鄰接點，然后分別從這些鄰接點出發(fā)按廣度優(yōu)先搜索的順序遍歷圖，直至圖中所有可被訪問的結(jié)點都被訪問到。序遍歷圖，直至圖中所有可被訪問的結(jié)點都被訪問到rocedure bfs(i:integer);/ bfs.pas var j,k:integer; begin fillchar(q,sizeof(q),0); open:=0; closed:=1; q1:=i; write(i, ); fi:=t

18、rue; while openclosed do begin inc(open); k:=qopen; for j:=1 to n do if (ak,j=1)and(fj=false) then begin write(j, ); fj:=true; inc(closed); qclosed:=j; end; end; end;3、圖的遍歷的簡單應(yīng)用、圖的遍歷的簡單應(yīng)用1 1、犯罪團(tuán)伙、犯罪團(tuán)伙 警察抓到了警察抓到了n n個罪犯，警察根據(jù)經(jīng)驗知道他們屬于不同的犯罪團(tuán)伙，卻個罪犯，警察根據(jù)經(jīng)驗知道他們屬于不同的犯罪團(tuán)伙，卻不能判斷有多少個團(tuán)伙，但通過警察的審訊，知道其中的一些罪犯之間相不能判斷

19、有多少個團(tuán)伙，但通過警察的審訊，知道其中的一些罪犯之間相互認(rèn)識，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識。有可能一個犯罪互認(rèn)識，已知同一犯罪團(tuán)伙的成員之間直接或間接認(rèn)識。有可能一個犯罪團(tuán)伙只有一個人。請你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。團(tuán)伙只有一個人。請你根據(jù)已知罪犯之間的關(guān)系，確定犯罪團(tuán)伙的數(shù)量。已知罪犯的編號從已知罪犯的編號從1 1至至n n。輸入：輸入：第一行：第一行：n n（=1000,=1000,罪犯數(shù)量），罪犯數(shù)量），第二行：第二行：m m（50005000，關(guān)系數(shù)量），關(guān)系數(shù)量）以下若干行：每行兩個數(shù)：以下若干行：每行兩個數(shù)：i i 和和j j，中間一個空格隔開，表示

20、罪犯，中間一個空格隔開，表示罪犯i i和罪犯和罪犯j j相互認(rèn)識。相互認(rèn)識。輸出：輸出：一個整數(shù)，犯罪團(tuán)伙的數(shù)量。一個整數(shù)，犯罪團(tuán)伙的數(shù)量。樣例輸入：11 8 1 24 35 41 35 67 105 108 9輸出：3說明：共三個犯罪團(tuán)伙。把把n個人看成圖的個人看成圖的n個頂點；相互認(rèn)識的連一條邊。個頂點；相互認(rèn)識的連一條邊。相互認(rèn)識的所有人構(gòu)成一個極大連通子圖。相互認(rèn)識的所有人構(gòu)成一個極大連通子圖。問題轉(zhuǎn)化為：問題轉(zhuǎn)化為：求無向圖的連通分量求無向圖的連通分量 （有多少個極大連通子圖）（有多少個極大連通子圖） procedure main; var i:integer; begin sum:

21、=0; fillchar(f,sizeof(f),false); for i:=1 to n do if not fi then begin inc(sum); dfs(i); end; writeln(sum); end;12354672、郵遞員郵遞員 郵遞員在送信時，為了節(jié)省路途，自己規(guī)定：每次總是從n個村子中選擇其中一個合適的村子出發(fā)，途中每個村子僅且經(jīng)過一次，送完所有的信。已知各個村子的道路連通情況。請你幫郵遞員選擇一條合適的路線。輸入：第一行：整數(shù)n：村子的個數(shù)。接下來是一個n*n的0、1矩陣，表示n個村子的連同情況，如：ai,j=1 ，表示第i和第j個村子之間有路可走，如果ai,j

22、=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分析：分析： 郵遞員從某一個村子郵遞員從某一個村子a出發(fā)；每個村子訪問僅且訪問一次，最后到出發(fā)；每個村子訪問僅且訪問一次，最后到達(dá)村子達(dá)村子b結(jié)束，從結(jié)束，從a到到b的路線成為的路線成為哈密頓路哈密頓路。 如果如果a和和b重合，即回到出發(fā)點，稱為重合，即回到出發(fā)點，稱為哈密頓回路哈密頓回路。b:array1.maxn of in

23、teger; /記錄哈密頓路記錄哈密頓路procedure main; var i:integer; begin for i:= 1 to n do begin fillchar(visited,sizeof(visited),false); b1:=i; visitedi:=true; dfs(i,1); end; print(0); end;procedure dfs(i,k:integer);/當(dāng)前已找到有當(dāng)前已找到有k個點，要搜第個點，要搜第k+1個點個點 var j:integer; begin if k=n then print(1); for j:=1 to n do if (a

24、j,i=1) and (visitedj=false) then begin visitedj:=true; bk+1:=j;/找到第找到第k+1個點并記下個點并記下 dfs(j,k+1); visitedj:=false; /回溯回溯 end; end;怎樣求哈密頓回路？怎樣求哈密頓回路？ 3 3 、安排座位、安排座位 n n個客人圍著一個桌子吃飯，每一個人都至少認(rèn)識其他的個客人圍著一個桌子吃飯，每一個人都至少認(rèn)識其他的2 2個客人。請設(shè)計程序個客人。請設(shè)計程序求得求得n n個人的一種坐法，使得每個人都認(rèn)識他左右的客人。個人的一種坐法，使得每個人都認(rèn)識他左右的客人。輸入輸入: :第一行第一行

25、:n:n（吃飯人的個數(shù)）。（吃飯人的個數(shù)）。以下以下n n行：第行：第i i行的第一個數(shù)行的第一個數(shù)k k表示第表示第i i個人認(rèn)識的人數(shù)，后面?zhèn)€人認(rèn)識的人數(shù)，后面k k個數(shù)依次為個數(shù)依次為i i認(rèn)識的認(rèn)識的人的編號。人的編號。輸出：所有座法，要求第一個人為輸出：所有座法，要求第一個人為1 1號作為起點，按順時針輸出其它人的編號。號作為起點，按順時針輸出其它人的編號。樣例輸入：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 34 4、素數(shù)鏈、素數(shù)鏈設(shè)計程序?qū)⒃O(shè)計

26、程序?qū)? 1。n n（2020）排成一排，使任意兩個相鄰的數(shù)的和為素數(shù)。）排成一排，使任意兩個相鄰的數(shù)的和為素數(shù)。第第1 1個和最后一個的和也為素數(shù)個和最后一個的和也為素數(shù). .輸出輸出: :第一個數(shù)為第一個數(shù)為1.1.四、無向圖的傳遞閉包四、無向圖的傳遞閉包判斷無向圖的連通性判斷無向圖的連通性1234657輸入圖的邊的信息，輸出輸入圖的邊的信息，輸出各點的連通行。各點的連通行。輸入：輸入：71 22 31 33 45 66 7輸出：輸出：1 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

27、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 鄰接矩陣鄰接矩陣判斷結(jié)點判斷結(jié)點 i 和和 j的連通性：的連通性：ijk1、結(jié)點、結(jié)點i和和j如果原來有邊則連通。如果原來有邊則連通。2、如果、如果i和和j之間沒有邊：之間沒有邊： 如果存在另外的一個結(jié)點如果存在另外的一個結(jié)點k，滿足：，滿足：i與與k連通，連通，k與與j連通，則連通，則i與與j連通。連通。 否則否則i和和j不連通。不連通。can i , j :

28、 true ，i與與j之間有邊；之間有邊；false：無邊。：無邊。則：則：can i , j =can i , j or ( can i , k and can k , j ) 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 and cank,j);過程：過程：產(chǎn)生數(shù)產(chǎn)生數(shù)【問題描述【問題描述:】給出一個正整數(shù)給出一個正整數(shù) n（n1050) 和和 k 個變換規(guī)則（個變換規(guī)則（k 5 3 6上面的整數(shù)上面的整數(shù) 234 經(jīng)過變換后可能產(chǎn)生出的整數(shù)為（包括原數(shù)）經(jīng)過變換后可能產(chǎn)生出的整數(shù)為

29、（包括原數(shù)）:234 534 264 564 共共 4 種不同的產(chǎn)生數(shù)。種不同的產(chǎn)生數(shù)?！救蝿?wù)：【任務(wù)：】給出一個整數(shù)給出一個整數(shù) n 和和 k 個變換規(guī)則。個變換規(guī)則。求經(jīng)過任意次的變換（求經(jīng)過任意次的變換（0次或多次），能產(chǎn)生出多少個不同整數(shù)。僅要求輸出個數(shù)。次或多次），能產(chǎn)生出多少個不同整數(shù)。僅要求輸出個數(shù)。 【輸入：【輸入：】第一行：第一行：n。第二行：。第二行：k。以下。以下k行：每行兩個一位數(shù)：行：每行兩個一位數(shù)：x y，中間一個空格，表示一個，中間一個空格，表示一個變換規(guī)則：變換規(guī)則：x可以變?yōu)榭梢宰優(yōu)閥?！据敵觯骸据敵觯骸恳粋€整數(shù)（滿足條件的個數(shù)）：一個整數(shù)（滿足條件的個數(shù)）：

30、 【輸入樣例：【輸入樣例：】234 22 53 6【樣例輸出：【樣例輸出：】4應(yīng)用舉例應(yīng)用舉例 本題搜索顯然是不行的。本題搜索顯然是不行的。 對于只需計數(shù)而不需求具體方案的題目，一般都不會用搜索解決。對于只需計數(shù)而不需求具體方案的題目，一般都不會用搜索解決。 分析：分析： 乘法原理直接進(jìn)行計數(shù)。乘法原理直接進(jìn)行計數(shù)。 用用fi表示數(shù)字表示數(shù)字i包括本身可以變成的數(shù)字總個數(shù)包括本身可以變成的數(shù)字總個數(shù) 這里的變成可以是直接變成也可以是間接變成：這里的變成可以是直接變成也可以是間接變成： 比如比如 3-5, 5-7,那么那么 3-7那么對于一個數(shù)那么對于一個數(shù)a（用數(shù)組存（用數(shù)組存,長度為長度為n

31、），根據(jù)乘法原理它能產(chǎn)生出），根據(jù)乘法原理它能產(chǎn)生出不同整數(shù)數(shù)量：不同整數(shù)數(shù)量：fa1*fa2*fa3*fan 引例引例：現(xiàn)在，我們想從城市現(xiàn)在，我們想從城市a a到達(dá)城市到達(dá)城市e e。怎樣走才能使得路徑最短，最短路徑的長度是多少？怎樣走才能使得路徑最短，最短路徑的長度是多少？ 1234567891011531638438556343五、圖的最短路徑五、圖的最短路徑已知各個城市之間的道路情況如下：已知各個城市之間的道路情況如下：圖中兩點間的最短距離。圖中兩點間的最短距離。兩類問題：兩類問題：1、圖中每對頂點（任意兩點）之間的最短路徑、圖中每對頂點（任意兩點）之間的最短路徑 （弗洛伊德算法：（

32、弗洛伊德算法：floyed）。）。2、圖中一個頂點到其他頂點的最短路徑、圖中一個頂點到其他頂點的最短路徑 （迪杰斯特拉算法：（迪杰斯特拉算法：dijkstra）。）。一）、計算每一對頂點間的最短路徑（一）、計算每一對頂點間的最短路徑（floyd算法）算法）目標(biāo)：把圖中任意兩點目標(biāo)：把圖中任意兩點i與與j之間的最短距離都求出來之間的最短距離都求出來 di,j。原理：根據(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

33、 di,k+dk,jdi,j then di,j:=di,k+dk,j;算法寫法算法寫法1：floyed2.pas初始化條件：初始化條件：d i, i =0 /自己到自己為自己到自己為0；對角線為；對角線為0；di,j=邊權(quán)，邊權(quán)，i與與j有直接相連的邊有直接相連的邊di,j= + ，i與與j無直接相連的邊。無直接相連的邊。 / 一般設(shè)為：一般設(shè)為： maxint or maxlongint;舉例：舉例： 已知下圖中給定的關(guān)系，求出圖中任意給定兩點之間的最短距離已知下圖中給定的關(guān)系，求出圖中任意給定兩點之間的最短距離123452317549137輸入：輸入：51 51 2 231 3 171

34、5 492 3 52 4 134 5 7要求：輸出最短距離要求：輸出最短距離d1,5。 / floyed2.pas分析：分析：di,j:表示頂點表示頂點i到頂點到頂點j之間的最短距離。之間的最短距離。初始化如下：初始化如下：0 23 17 23 0 5 15 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 floyedprocedure init; readln(n); readln(p,q); for i:=1 to n do for j:=

35、1 to n do if i=j then di,j:=0 else di,j:=maxint; 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,jdi,j then di,j:=di,k+dk,j; end;procedure print; begin writeln(dp,q); end;算法寫法算法寫法2：floyed1.pas0 23 1

36、7 0 023 0 5 15 017 5 0 0 00 13 0 0 749 0 0 7 0初始化：無邊的全都為初始化：無邊的全都為0procedure init; fillchar(d,sizeof(d),0); readln(n); readln(p,q); while not seekeof do begin readln(i,j,w); di,j:=w; dj,i:=w; end;/ floyedfor k:=1 to n do for i:=1 to n do if (ki)and(di,k0) then for j:=1 to n do if (kj)and(ij)and(dk,j

37、0) then if (di,j=0)or(di,k+dk,j2: 22: 1 3 2 1-3: 17: 1 3 1-4: 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è)設(shè) pathi,j 記錄記錄i到到j(luò)的最短路徑中的最短路徑中j的前驅(qū)頂點。的前驅(qū)頂點。如樣例：如樣例：1-4: 35: 1 3 2 4 path1,4=2path1,2=3path1,3=1初始化：初始化：

38、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,k+dk,j0 then begin dfs(i,pathi,j); write(j, ); end; end;ipathi,jj方法二：方法二：floyed4.pas設(shè)設(shè) pathi,j 記錄能使記錄能使i到到j(luò)的距離變短的結(jié)點。的距離變短的結(jié)點。初始化：初始化：pathi,j= -1: i與與j不通的不通的pathi,j:=0; 從從i到到j(luò)的最短路徑是直接到達(dá)的。開始有邊的都直接到達(dá)。的最短路徑是直接到

39、達(dá)的。開始有邊的都直接到達(dá)。pathi,j0;從從i到到j(luò)的最短路徑要經(jīng)過點的最短路徑要經(jīng)過點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(pathi,j, ); dfs(pathi,j,j); end; end;輸出輸出i到到j(luò)的最短路徑：的最短路徑：write(i); dfs(i,j); write(j);總結(jié)：總結(jié)：floyed算法：算法：要求某兩點之間要求某兩點之間 u 到到 v 的最短距離，先求出任意兩點之間的距離，的最

40、短距離，先求出任意兩點之間的距離，然后然后writeln(du,v)時間復(fù)雜度：時間復(fù)雜度：o（n3）二）、計算某一頂點到其它所有頂點的最短路徑二）、計算某一頂點到其它所有頂點的最短路徑 （單源最短路徑問題：（單源最短路徑問題：dijkstra 算法）算法）開始點（源點）：開始點（源點）：startdi:頂點到頂點到st的最短距離。的最短距離。初始：初始：dstart=0；di=ast,istart其它其它n-1個點個點集合集合1：已求點：已求點集合集合2：未求點：未求點1、在集合、在集合2中找一個到中找一個到start距離最近的頂點距離最近的頂點k ，距離，距離=dk2、把頂點、把頂點k加到

41、集合加到集合1中，同時修改集合中，同時修改集合2 中的剩余頂點中的剩余頂點j的的dj是否經(jīng)過是否經(jīng)過k后變短。如果變短修改后變短。如果變短修改djif dk+ak,jdj then dj=dk+ak,j3、重復(fù)、重復(fù)1，直至集合，直至集合2空為止?？諡橹埂?for i:=1 to n do begin di:=astart,i; fi:=false; end; fstart:=true; / 加入集合加入集合1 for i:=2 to n do begin min:=maxint; for j:=1 to n do if (not fj) and (djmin) then begin min:

42、=dj; k:=j; end; fk:=true; / 加入集合加入集合1 for j:=1 to n do /修改集合修改集合2中的中的dj if (not fj) and (dk+ak,j2: 22: 1 3 2 1-3: 17: 1 3 1-4: 35: 1 3 2 4 1-5: 42: 1 3 2 4 5 怎樣輸出路徑？怎樣輸出路徑？六、圖的最小生成樹六、圖的最小生成樹普里姆算法（普里姆算法（prim）克魯斯卡爾（克魯斯卡爾（kruskal）網(wǎng)絡(luò)建設(shè)網(wǎng)絡(luò)建設(shè)net.pas/net.in/net.out【問題描述：【問題描述：】oi國由國由n個城市組成，所有城市位于一平面坐標(biāo)系中，每個城

43、市的坐標(biāo)是已知個城市組成，所有城市位于一平面坐標(biāo)系中，每個城市的坐標(biāo)是已知的，且坐標(biāo)都是整數(shù)?，F(xiàn)在，的，且坐標(biāo)都是整數(shù)?，F(xiàn)在，oi國的國的chen主席想加快網(wǎng)絡(luò)信息傳遞，決定主席想加快網(wǎng)絡(luò)信息傳遞，決定選若干對城市，每對城市之間用一條高速網(wǎng)線相連，并且使所有的城市都可選若干對城市，每對城市之間用一條高速網(wǎng)線相連，并且使所有的城市都可以直接或間接相連。已知兩城市之間的距離為它們的直線距離，求所需網(wǎng)線以直接或間接相連。已知兩城市之間的距離為它們的直線距離，求所需網(wǎng)線的最小長度。的最小長度?！据斎耄骸据斎耄骸縩n行，每行有兩個整數(shù)行，每行有兩個整數(shù)x , y 表示第表示第i個城市的坐標(biāo)為個城市的坐標(biāo)

44、為 (x , y )【輸出：【輸出：】最短的網(wǎng)線的長度。最短的網(wǎng)線的長度。 結(jié)果保留結(jié)果保留3為小數(shù)。為小數(shù)?！据斎霕永骸据斎霕永骸?2 14 15 43 53 32 3【輸出樣例：【輸出樣例：】9.236數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)模 n=500 1= x, y =10000 1 2 3 4 5 621345612435173010247235最小生成樹：最小生成樹： 含有含有n個結(jié)點的圖，從中選個結(jié)點的圖，從中選n-1條邊，保持條邊，保持n個點個點中任意兩點是連通的，并且中任意兩點是連通的，并且n-1條邊的和最小。這條邊的和最小。這n個個點和這點和這n-1條邊就成為原圖的最小生成樹。條邊就成為原圖的

45、最小生成樹。任意結(jié)點開始（不妨設(shè)為任意結(jié)點開始（不妨設(shè)為v1）構(gòu)造最小生成樹：）構(gòu)造最小生成樹：首先把這個結(jié)點包括進(jìn)生成樹里，然后在那些其一個端首先把這個結(jié)點包括進(jìn)生成樹里，然后在那些其一個端點已在生成樹里、另一端點還未在生成樹里的所有邊中點已在生成樹里、另一端點還未在生成樹里的所有邊中找出權(quán)最小的一條邊，并把這條邊、包括不在生成樹的找出權(quán)最小的一條邊，并把這條邊、包括不在生成樹的另一端點包括進(jìn)生成樹，另一端點包括進(jìn)生成樹，。依次類推，直至將所有結(jié)。依次類推，直至將所有結(jié)點都包括進(jìn)生成樹為止。點都包括進(jìn)生成樹為止。 普里姆算法（普里姆算法（prim）1243517301024723512345

46、 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:=ak,j; end;prim算法描述：算法描述：/ai，j：i到到j(luò)的邊長

47、。的邊長。/di：結(jié)點：結(jié)點i到生成樹中結(jié)點的最短距離到生成樹中結(jié)點的最短距離/fi:true:在生成樹種，在生成樹種，false：不在生成樹中。：不在生成樹中。輸入：輸入：51 2 231 3 171 5 492 3 52 4 134 5 7輸出最小生成樹的邊：輸出最小生成樹的邊：pre:array1.maxn of integer; prei:點點i的前驅(qū)點的前驅(qū)點tree:array1.maxn-1,1.2 of integer; 記錄邊記錄邊 for i:=1 to n do begin di:=a1,i; prei:=1; fi:=false; end; f1:=true; ans:

48、=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 do if (not fj) and(ak,jdj) then begin dj:=ak,j; prej:=k; end; end;克魯斯卡爾（克魯斯卡爾（kruskal）算法步驟：算法步驟：1、把圖中的邊按權(quán)值從小到大排序。、把圖中的邊按權(quán)值

49、從小到大排序。2、按從小到大的順序依次向樹中加邊。、按從小到大的順序依次向樹中加邊。 在添加每一條邊（在添加每一條邊（u，v）時，如果）時，如果u和和v兩個點都已在樹中，一兩個點都已在樹中，一旦添加，就回構(gòu)成回路，所以放棄該邊，在向后找下一條邊。旦添加，就回構(gòu)成回路，所以放棄該邊，在向后找下一條邊。3、直到添加、直到添加n-1條邊。條邊。關(guān)鍵：加邊時不能構(gòu)成回路：邊的兩個頂點是否已在樹種。關(guān)鍵：加邊時不能構(gòu)成回路：邊的兩個頂點是否已在樹種。1243517301024723512345type node=record data:integer; u,v:integer; end;var e:array1.maxn*(maxn-1) div 2 of node; /邊邊 f:array1.maxn of integer; /父親接點父親接點 n,m:integer; ans:integer; readln(n); m:=0; while not seekeof do begin readln(i,j,k); inc(m); em.data:=k; em.u:=i; em.v:=j; end; procedure kruskal; var i:inte