第七章圖PPT課件

1、1第七章 圖2v 圖圖g由兩個集合由兩個集合v和和e組成，記為組成，記為g=(v,e),其中其中v為頂點(diǎn)為頂點(diǎn)的的有窮非空集有窮非空集合，合，e為為v中中頂點(diǎn)偶對頂點(diǎn)偶對(即邊即邊)的集合。圖的集合。圖g的的頂點(diǎn)集和邊集分別記為頂點(diǎn)集和邊集分別記為v(g)和和e(g)。e(g)可以是空集，可以是空集，若若e(g)為空，則圖為空，則圖g只有頂點(diǎn)而沒有邊。只有頂點(diǎn)而沒有邊。7.1 7.1 圖的概念圖的概念3一條邊是由兩個頂點(diǎn)組成的有一條邊是由兩個頂點(diǎn)組成的有序?qū)?，記為序?qū)Γ洖?。一般地。一般地表示一條有向邊，表示一條有向邊，vi為為邊的起點(diǎn)，邊的起點(diǎn)，vj為邊的終點(diǎn)。有為邊的終點(diǎn)。有向邊又稱為向

2、邊又稱為弧弧，vi為為弧尾弧尾，vj為為弧頭弧頭.v(g)=v1,v2,v3,v4,v5e(g )=,7.1v 有向圖有向圖: :圖圖g g中的每一條邊都是有方向的中的每一條邊都是有方向的。v2v3v4v5v14v無向圖無向圖: 圖中的每一條邊都是無方向的。圖中的每一條邊都是無方向的。一條邊為兩個頂點(diǎn)的無序?qū)σ粭l邊為兩個頂點(diǎn)的無序?qū)?記為記為(v1,v4)。一般地。一般地(vi,vj)表表示一條無向邊，并且示一條無向邊，并且(vi,vj)和和(vj,vi)表示同一條邊表示同一條邊v(g)=v1,v2,v3,v4,v5e(g)= (v1,v2),(v1,v3),(v1,v4),(v2,v3),(

3、v2,v5),(v4,v5)7.1v2v3v4v5v157.1v若若 (vi,vj) 是是一條無向邊，則稱頂點(diǎn)一條無向邊，則稱頂點(diǎn) vi 和和 vj 互為互為鄰接點(diǎn)鄰接點(diǎn)(adjacent)，(vi,vj) 與頂點(diǎn)與頂點(diǎn) vi 和和 vj 相關(guān)聯(lián)相關(guān)聯(lián)(incident)。v若若 是一條有向邊，則稱頂點(diǎn)是一條有向邊，則稱頂點(diǎn) vi 鄰接到鄰接到 vj，頂點(diǎn)，頂點(diǎn) vj 鄰鄰接于接于vi， 與頂點(diǎn)與頂點(diǎn) vi 和和 vj 相關(guān)聯(lián)。相關(guān)聯(lián)。v無向完全圖無向完全圖任何兩個頂點(diǎn)之間都有邊的無向圖。共有任何兩個頂點(diǎn)之間都有邊的無向圖。共有 n(n-1)/2 條邊。條邊。v有向完全圖有向完全圖任何兩個頂點(diǎn)

4、之對間都有弧的有向圖。共有任何兩個頂點(diǎn)之對間都有弧的有向圖。共有n(n-1)條邊。條邊。無向完全圖無向完全圖有向完全圖有向完全圖67.1度、入度和出度的概念：度、入度和出度的概念： 無向圖中無向圖中頂點(diǎn)頂點(diǎn)v的度的度為關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，記為為關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，記為d(v)有向圖中把以頂點(diǎn)有向圖中把以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為為終點(diǎn)的邊的數(shù)目稱為v的的入度入度，記為，記為id(v) 把以頂點(diǎn)把以頂點(diǎn)v為始點(diǎn)的邊的數(shù)目稱為為始點(diǎn)的邊的數(shù)目稱為v的的出度出度,記為記為od(v) 頂點(diǎn)的度頂點(diǎn)的度定義為入度與出度之和，即定義為入度與出度之和，即d(v)=id(v)+od(v)v2v3v4v

5、5v1 e = d(vi)/2ni=1d(v1)=d(v2)=3d(v3)=2 d(v4)=d(v5)=3id(v2)=1,od(v2)=2d(v2)=id(v2)+od(v2)=3v2v3v4v5v1無論有向圖還是無向圖，頂點(diǎn)數(shù)無論有向圖還是無向圖，頂點(diǎn)數(shù) n 邊數(shù)邊數(shù) e 和度之間的關(guān)系滿足：和度之間的關(guān)系滿足：d(v1)=d(v2)=3d(v3)=d(v4)=d(v5)= 27v子圖的概念子圖的概念:設(shè)設(shè)g=(v,e)是一個圖，若是一個圖，若v是是v的子集，的子集，e是是e的子集且的子集且e中的邊所關(guān)聯(lián)的頂點(diǎn)均在中的邊所關(guān)聯(lián)的頂點(diǎn)均在v中中，則，則g=(v,e)也是一個圖，并稱其為也是一

6、個圖，并稱其為g的的子圖子圖。若若v=v1,v2 , e=(v1,v3) ,g=(v,e)不是圖不是圖 , 也不可能是子圖。也不可能是子圖。7.1v2v3v4v5v18路徑路徑：若存在一個頂點(diǎn)序列若存在一個頂點(diǎn)序列vp,vi1,vi2,vin,vq:無向圖無向圖g中中,使得使得(vp,vi1),(vi1,vi2),(vin,vq) 均屬于均屬于e(g),則則稱頂點(diǎn)稱頂點(diǎn)vp到到vq存在一條路徑。存在一條路徑。有向圖有向圖g中中,若若,均屬于均屬于e(g),則則從頂點(diǎn)從頂點(diǎn)vp到到vq存在一條路徑。存在一條路徑。 7.1路徑長度路徑長度：路徑長度為該路徑上邊的數(shù)目。：路徑長度為該路徑上邊的數(shù)目。

7、 v2v3v4v5v1該有向圖中頂點(diǎn)該有向圖中頂點(diǎn)v2到頂點(diǎn)到頂點(diǎn)v3、 v4和和v5存在路徑，存在路徑，到到v1不存在路徑不存在路徑9例例1 從從v1 v5路徑路徑 v1 v2 v3 v4 v2 v5不是簡單路徑不是簡單路徑路徑路徑 v1 v2 v5是簡單路徑是簡單路徑v1 v2 v3 v4 v2 v5 v1是個回路，但不是個回路，但不是簡單回路是簡單回路而而v1 v2 v5 v1 是簡單回路是簡單回路7.1簡單路徑簡單路徑：除起點(diǎn)和終點(diǎn)外，其余頂點(diǎn)均不相同的路徑稱：除起點(diǎn)和終點(diǎn)外，其余頂點(diǎn)均不相同的路徑稱為為簡單路徑簡單路徑。起點(diǎn)和終點(diǎn)相同的簡單路徑稱為。起點(diǎn)和終點(diǎn)相同的簡單路徑稱為簡單回

8、路簡單回路。v1v2v3v4v510有向圖的根有向圖的根有向圖中，若存在一個頂點(diǎn)有向圖中，若存在一個頂點(diǎn)v，從該頂點(diǎn)到圖中其它各頂點(diǎn)，從該頂點(diǎn)到圖中其它各頂點(diǎn)都存在路徑，則稱該有向圖為都存在路徑，則稱該有向圖為有根圖有根圖，v稱為圖的稱為圖的根根。v1為根為根7.1v2v3v4v5v111v有向圖有向圖g g中，任意兩個不同的頂點(diǎn)中，任意兩個不同的頂點(diǎn)vivi和和vj,vj,都存在從都存在從vivi到到 vjvj以及以及vjvj到到vivi的的 路徑，則稱路徑，則稱g g為為強(qiáng)連通圖強(qiáng)連通圖。v有向圖有向圖g g的極大強(qiáng)連通子圖稱為的極大強(qiáng)連通子圖稱為g g的的強(qiáng)連通分量強(qiáng)連通分量。7.1v無

9、向圖無向圖g g中，若任意兩個頂點(diǎn)間存在路徑中，若任意兩個頂點(diǎn)間存在路徑( (即連通的即連通的),),則稱則稱g g為為連通圖連通圖。v無向圖無向圖g g的極大連通子圖稱為的極大連通子圖稱為g g的的連通分量連通分量。v1v2v3v4v5非連通圖非連通圖g的兩個連通分量的兩個連通分量強(qiáng)連通圖只有強(qiáng)連通圖只有一個一個強(qiáng)連通分量強(qiáng)連通分量非強(qiáng)連通圖有非強(qiáng)連通圖有多個多個強(qiáng)連通分量強(qiáng)連通分量12注意：注意：帶權(quán)圖中權(quán)值的含義視具體問題而定帶權(quán)圖中權(quán)值的含義視具體問題而定(距離、耗費(fèi)等距離、耗費(fèi)等).v若將圖中的每一條邊賦上一個權(quán)值，則稱該圖為若將圖中的每一條邊賦上一個權(quán)值，則稱該圖為帶權(quán)帶權(quán)圖圖。帶

10、權(quán)圖又稱為。帶權(quán)圖又稱為網(wǎng)絡(luò)網(wǎng)絡(luò)。381752帶權(quán)圖帶權(quán)圖v2v3v4v5v113 圖的存儲涉及到兩方面：頂點(diǎn)內(nèi)容的存儲和邊圖的存儲涉及到兩方面：頂點(diǎn)內(nèi)容的存儲和邊( (邏輯邏輯關(guān)系關(guān)系) )的存儲。圖的存儲所采用的兩種常用方法為：的存儲。圖的存儲所采用的兩種常用方法為：鄰接鄰接矩陣矩陣和和鄰接表鄰接表。7.2.1 7.2.1 鄰接矩陣表示法鄰接矩陣表示法7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)1.鄰接矩陣定義鄰接矩陣定義鄰接矩陣鄰接矩陣指的是表示圖中頂點(diǎn)之間相鄰關(guān)系的矩陣。指的是表示圖中頂點(diǎn)之間相鄰關(guān)系的矩陣。7.214設(shè)設(shè)g=(v,e)是具有是具有n個頂點(diǎn)的圖，則個頂點(diǎn)的圖，則g的鄰接矩陣

11、為具有如下的鄰接矩陣為具有如下性質(zhì)的性質(zhì)的n階方陣：階方陣： 1：若：若 (vi+1,vj+1) 或或 是是e(g)中的邊中的邊 ai,j= 0：若：若(vi+1,vj+1) 或或 不是不是e(g)中的邊中的邊v有向圖（無向圖）的有向圖（無向圖）的鄰接矩陣鄰接矩陣15a=0 1 1 1 00 0 1 0 10 0 0 0 00 0 0 0 10 0 0 1 0鄰接矩陣鄰接矩陣有向圖的鄰接矩陣通常是有向圖的鄰接矩陣通常是非對稱非對稱的的7.2鄰接矩陣鄰接矩陣a=0 1 1 1 01 0 1 0 11 1 0 0 01 0 0 0 10 1 0 1 0無向圖的鄰接矩陣是無向圖的鄰接矩陣是對稱對稱的

12、的v2v3v4v5v1v2v3v4v5v116鄰接矩陣鄰接矩陣a=0 3 5 1 03 0 2 0 85 2 0 0 01 0 0 0 70 8 0 7 0網(wǎng)絡(luò)的鄰接矩陣定義為：網(wǎng)絡(luò)的鄰接矩陣定義為： wij:若若 (vi+1,vj+1) 或或 是是e(g)中的邊中的邊 ai,j= 0或或 :若若 (vi+1,vj+1) 或或 不是不是e(g)中的邊中的邊381752帶權(quán)圖帶權(quán)圖v2v3v4v5v117 2.鄰接矩陣存儲結(jié)構(gòu)描述：鄰接矩陣存儲結(jié)構(gòu)描述： #define n . /* 圖中頂點(diǎn)個數(shù)圖中頂點(diǎn)個數(shù) */ #define e . /* 圖中邊圖中邊(弧弧)條數(shù)條數(shù) */ typedef

13、 char vextype; /* 頂點(diǎn)數(shù)據(jù)類型頂點(diǎn)數(shù)據(jù)類型 */ typedef float adjtype; /* 權(quán)值類型權(quán)值類型 */ typedef struct vextype vexsn; /* 數(shù)組數(shù)組vexs 用于存儲頂點(diǎn)數(shù)據(jù)用于存儲頂點(diǎn)數(shù)據(jù) */ adjtype arcsnn; /* arcs 為鄰接矩陣為鄰接矩陣 */ graph; 若圖中頂點(diǎn)信息僅為編號若圖中頂點(diǎn)信息僅為編號, 則僅需存儲一個鄰接矩陣即可表示圖。則僅需存儲一個鄰接矩陣即可表示圖。18 scanf(%d%d%f,&i,&j,&w); ga arcsi-1j-1=w; /*有向網(wǎng)有向

14、網(wǎng)*/ scanf(%d%d%f,&i,&j,&w); ga arcsi-1j-1=1; /*有向圖有向圖*/ scanf(%d%d,&i,&j); ga arcsi-1j-1=1; /*若為無向圖若為無向圖*/ ga arcsj-1i-1=1; scanf(%d%d%f,&i,&j,&w); ga arcsi-1j-1=w; /*因?yàn)槭菬o向網(wǎng)因?yàn)槭菬o向網(wǎng)*/ ga arcsj-1i-1=w; 建立一個采用鄰接矩陣表示法實(shí)現(xiàn)存儲的建立一個采用鄰接矩陣表示法實(shí)現(xiàn)存儲的無向網(wǎng)無向網(wǎng)的算法如下：的算法如下：creatgraph(ga)g

15、raph ga; int i,j,k; float w; for(i=0;in;i+) ga vexsi=getchar( ); for(i=0;in;i+) for(j=0;jn;j+) ga arcsij=0; /*初始化鄰接矩陣初始化鄰接矩陣*/ for(k=0;ke;k+)3.建立鄰接矩陣建立鄰接矩陣7.2該算法的時間復(fù)雜度為該算法的時間復(fù)雜度為 o(n+n2+e) , 因?yàn)橐驗(yàn)?en2 ,所以為所以為 o(n2)19 adjvex next7.2.2 7.2.2 鄰接表表示法鄰接表表示法 鄰接表表示法類似于樹的孩子鏈表表示法。對于圖鄰接表表示法類似于樹的孩子鏈表表示法。對于圖g g中

16、的某一個頂點(diǎn)中的某一個頂點(diǎn)vivi，將鄰接于它的所有頂點(diǎn)鏈成一個單，將鄰接于它的所有頂點(diǎn)鏈成一個單鏈表，該單鏈表稱為鏈表，該單鏈表稱為頂點(diǎn)頂點(diǎn)vivi的鄰接表的鄰接表。鄰接表中結(jié)點(diǎn)的結(jié)構(gòu)如下：鄰接表中結(jié)點(diǎn)的結(jié)構(gòu)如下：鄰接點(diǎn)域鄰接點(diǎn)域:存放鄰接于頂點(diǎn)存放鄰接于頂點(diǎn)vi的結(jié)點(diǎn)的序號的結(jié)點(diǎn)的序號j鏈域鏈域:存放指向下一個存放指向下一個結(jié)點(diǎn)的指針結(jié)點(diǎn)的指針1、鄰接表定義、鄰接表定義7.2每個鄰接表均有一個表頭結(jié)點(diǎn)，該結(jié)點(diǎn)有每個鄰接表均有一個表頭結(jié)點(diǎn)，該結(jié)點(diǎn)有兩個域兩個域，分別存，分別存放頂點(diǎn)放頂點(diǎn)vi的信息和鄰接表中第一個結(jié)點(diǎn)的指針。的信息和鄰接表中第一個結(jié)點(diǎn)的指針。vertexlink頂點(diǎn)域頂點(diǎn)域

17、指針域指針域存放頂點(diǎn)的信息存放頂點(diǎn)的信息存放指向存放指向vi鄰接表中鄰接表中第一個結(jié)點(diǎn)的頭指針，第一個結(jié)點(diǎn)的頭指針，稱為鏈的表頭稱為鏈的表頭20將所有的表頭結(jié)點(diǎn)順序存儲在一個向量中，圖就可以用將所有的表頭結(jié)點(diǎn)順序存儲在一個向量中，圖就可以用這個表頭向量來表示這個表頭向量來表示.7.2v2v3v4v5v1v5v2v3v4v12343554v1v2v3v4v5vertex link鄰接表鄰接表234135121524v1v2v3v4v5vertex link鄰接表鄰接表v將無向圖的鄰接表稱為將無向圖的鄰接表稱為邊表邊表,將有向圖的鄰接表稱為將有向圖的鄰接表稱為出邊表出邊表21有向圖還有一種有向圖還

18、有一種逆鄰接表逆鄰接表為每個頂點(diǎn)為每個頂點(diǎn)vi建立一個建立一個入邊表入邊表 1 3 4 vertex link v1v2v3v4v512 3 2頂點(diǎn)表頂點(diǎn)表入邊表入邊表 5 逆鄰逆鄰接表接表7.2v3v1v2v4v522typedef strcutvextype vertex; edgenode *link; vexnode; /*頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)*/ 2.鄰接表存儲結(jié)構(gòu)描述：鄰接表存儲結(jié)構(gòu)描述： typedef struct node int adjvex; struct node *next edgenode; /*邊表結(jié)點(diǎn)結(jié)構(gòu)邊表結(jié)點(diǎn)結(jié)構(gòu)*/ adjvex nextverte

19、xlink頂點(diǎn)域頂點(diǎn)域 指針域指針域7.2vexnode gan;23鄰鄰接接表表vexnode ga25；vexnode ga14；7.2v3v1v2v4v5v1v4v2v34 21 1 1332 2 v1v2v3v4vertexlink4 頂點(diǎn)表頂點(diǎn)表邊表邊表5 4 2 1vertex linkv1v2v3v4v51 2 1 4 頂點(diǎn)表頂點(diǎn)表出邊表出邊表24 scanf(%d%d,&i,&j); s=malloc(sizeof(edgenode); sadjvex=i;snext=gaj-1.link;gaj-1.link=s; 生成有向生成有向圖的入邊表圖的入邊表 sca

20、nf(%d%d,&i,&j); s=malloc(sizeof(edgenode); sadjvex=j;snext=gai-1.link;gai-1.link=s; 生成有向生成有向圖的出邊表圖的出邊表 scanf(“%d%d”,&i,&j); s=malloc(sizeof(edgenode); / 生成邊表結(jié)點(diǎn)生成邊表結(jié)點(diǎn) sadjvex=j; snext=gai-1.link; gai-1.link=s; s=malloc(sizeof(edgenode); sadjvex=i; snext=gaj-1.link; gaj-1.link=s;生成無向生成

21、無向圖的邊表圖的邊表7.23.建立鄰接表的算法描述如下建立鄰接表的算法描述如下：creatadjlist(ga)vexnode ga ; int i,j,k; edgenode *s; for(i=0;in;i+)/*讀入頂點(diǎn)信息并初始化邊表頭指針讀入頂點(diǎn)信息并初始化邊表頭指針*/ gai.vertex=getchar( );gai.link=null; for(k=0;ke;k+) 生成無向圖的時間復(fù)雜度是生成無向圖的時間復(fù)雜度是o(n+e)o(n+e) 生成有向圖的時間復(fù)雜度是生成有向圖的時間復(fù)雜度是o(n+e)o(n+e)25(1) 一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一個圖

22、的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一。一。因?yàn)猷徑颖肀硎局?，各邊表結(jié)點(diǎn)的鏈接次序取決于因?yàn)猷徑颖肀硎局?，各邊表結(jié)點(diǎn)的鏈接次序取決于建立鄰接表的算法及邊的輸入次序。建立鄰接表的算法及邊的輸入次序。4.4.鄰接矩陣和鄰接表的比較：鄰接矩陣和鄰接表的比較：7.2(2) 在在鄰接表（或逆鄰接表）鄰接表（或逆鄰接表）表示中，每個邊表對應(yīng)于鄰接表示中，每個邊表對應(yīng)于鄰接矩陣矩陣一行（或一一行（或一 列）列）,邊表中結(jié)點(diǎn)個數(shù)等于邊表中結(jié)點(diǎn)個數(shù)等于一行（或一列）一行（或一列）中非零元素個數(shù)。中非零元素個數(shù)。(3) n個頂點(diǎn)個頂點(diǎn) e條邊的圖條邊的圖 建立建立 鄰接矩陣鄰接矩陣 鄰接表鄰接表 無向圖：無

23、向圖： o(n2) o(n+2e） 有向圖：有向圖： o(n2) o(n+e）26(4) 求頂點(diǎn)求頂點(diǎn)vi的度：的度： 鄰接矩陣鄰接矩陣 鄰接表鄰接表 無向圖：無向圖： 第第i行（列）上非零元素個數(shù)行（列）上非零元素個數(shù) 第第i個邊表中結(jié)點(diǎn)數(shù)個邊表中結(jié)點(diǎn)數(shù) 有向圖有向圖出度出度：第：第i行上非零元素個數(shù)行上非零元素個數(shù) 第第i個出邊表上的結(jié)點(diǎn)數(shù)個出邊表上的結(jié)點(diǎn)數(shù) 入度入度： 第第i列上非零元素個數(shù)列上非零元素個數(shù) 較難，需遍歷整個表較難，需遍歷整個表 4.4.鄰接矩陣和鄰接表的比較：鄰接矩陣和鄰接表的比較：(5) 判斷（判斷（vi，vj）或）或vi，vj是否是圖的一條邊是否是圖的一條邊 鄰接矩

24、陣鄰接矩陣：判矩陣中第：判矩陣中第i行行 第第j列的那個元素是否為零列的那個元素是否為零 鄰接表中鄰接表中：掃描第：掃描第i個邊表個邊表o(n)27(6) 求邊數(shù)求邊數(shù)e 鄰接矩陣鄰接矩陣：檢測整個矩陣：檢測整個矩陣 o(n2) 鄰接表鄰接表： 計(jì)算邊表結(jié)點(diǎn)個數(shù)之和計(jì)算邊表結(jié)點(diǎn)個數(shù)之和 o(e+n)7.2稠密圖稠密圖：對：對n個頂點(diǎn)的圖，若個頂點(diǎn)的圖，若e接近于接近于n*(n-1) （有向圖）或（有向圖）或 e接近于接近于n*(n-1)/2(無向圖無向圖)則稱該圖為稠密圖；則稱該圖為稠密圖；稀疏圖稀疏圖：對：對n個頂點(diǎn)的圖，若個頂點(diǎn)的圖，若en*(n-1) (有向圖有向圖) 或或 e v2 -

25、 v4 - v8 - v5 - v3 - v6 - v7特點(diǎn)：遍歷過程中盡可能地先對縱深方向進(jìn)行搜索特點(diǎn)：遍歷過程中盡可能地先對縱深方向進(jìn)行搜索v1v2v4v5v6v3v7v8fffff 假設(shè)從假設(shè)從v1開始出發(fā)進(jìn)行遍歷開始出發(fā)進(jìn)行遍歷:v1dfs (1)v2tv3tdfs (4)dfs (3)dfs (2)v5tv4tdfs (0)0 1 1 1 01 0 1 0 11 1 0 0 01 0 0 0 10 1 0 1 0int visitedn;graph g;dfs( i )int i;int j; printf(%c,g.vexsi); visitedi=true; for(j=0;jn

26、;j+) if(g.arcsij=1)&(!visitedj) dfs(j); i=0j=011j=211 1j=4111j=31 1i=1i=2i=1i=4i=3i=4i=1i=01 1 鄰接矩陣鄰接矩陣g.arcsnnprintf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)dfs(j);printf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)執(zhí)行結(jié)果執(zhí)行結(jié)果:tj=1j=0prin

27、tf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)printf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)dfs(j);printf(%c,g.vexsi);visitedi=true; for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj) for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj)dfs(j);printf(

28、%c,g.vexsi); for(j=0;jn;j+) if(g.arcsij=1)&(!visitedj) for(j=0;jadjvex-1) /*從從vi的未曾訪問過的鄰接點(diǎn)出的未曾訪問過的鄰接點(diǎn)出 發(fā)進(jìn)行深度優(yōu)先搜索發(fā)進(jìn)行深度優(yōu)先搜索*/ dfsl(p-adjvex-1); p=p-next; /*找找vi的下一鄰接點(diǎn)的下一鄰接點(diǎn)*/3839 對圖進(jìn)行深度優(yōu)先搜索得到的頂點(diǎn)序列稱為對圖進(jìn)行深度優(yōu)先搜索得到的頂點(diǎn)序列稱為注意注意7.3dfs序列序列不唯一，不唯一，它與遍歷它與遍歷算法，算法，圖的圖的存存儲結(jié)構(gòu)儲結(jié)構(gòu)以及以及初始出發(fā)點(diǎn)初始出發(fā)點(diǎn)有關(guān)有關(guān)。3.3.算法分析算法分析對于

29、具有對于具有n n個頂點(diǎn)、個頂點(diǎn)、e e條邊的連通圖條邊的連通圖： 算法的時間復(fù)雜度為算法的時間復(fù)雜度為: dfs-o(n2) dfsl-o(n+e) 算法的空間復(fù)雜度為算法的空間復(fù)雜度為o(n)407.3三、三、 連通圖的廣度優(yōu)先搜索遍歷連通圖的廣度優(yōu)先搜索遍歷(breadth first search)1. bfs基本思想基本思想 1）從圖）從圖g中任一頂點(diǎn)中任一頂點(diǎn)vi出發(fā)，訪問頂點(diǎn)出發(fā)，訪問頂點(diǎn)vi； 2）依次訪問）依次訪問vi的所有未曾過的鄰接點(diǎn)；的所有未曾過的鄰接點(diǎn)； 3）分別從這些鄰接點(diǎn)出發(fā)廣度優(yōu)先搜索遍歷圖。）分別從這些鄰接點(diǎn)出發(fā)廣度優(yōu)先搜索遍歷圖。41v1v2v4v5v6v3

30、v7v8v1 - v2 - v3 - v4 - v5 - v6 - v7 - v8特點(diǎn)：盡可能地先對橫向進(jìn)行搜索特點(diǎn)：盡可能地先對橫向進(jìn)行搜索。42 p2k2vip11 p12 p1k1p21 p22 p2i 一步一步能通達(dá)的坐標(biāo)點(diǎn)能通達(dá)的坐標(biāo)點(diǎn)二步二步能通達(dá)的坐標(biāo)點(diǎn)能通達(dá)的坐標(biāo)點(diǎn)r步步能通達(dá)的坐標(biāo)點(diǎn)能通達(dá)的坐標(biāo)點(diǎn) 2.2.算法實(shí)現(xiàn)算法實(shí)現(xiàn): :bfs算法符合算法符合先進(jìn)先出先進(jìn)先出性質(zhì)。在算法實(shí)現(xiàn)過程中，引入性質(zhì)。在算法實(shí)現(xiàn)過程中，引入隊(duì)列隊(duì)列作為輔助存儲結(jié)構(gòu)，存儲已被訪問的頂點(diǎn)。作為輔助存儲結(jié)構(gòu)，存儲已被訪問的頂點(diǎn)。43n在廣度優(yōu)先搜索遍歷中，先被訪問的頂點(diǎn)，在廣度優(yōu)先搜索遍歷中，先被訪問

31、的頂點(diǎn)，其鄰接點(diǎn)亦先被訪問，所以在算法的實(shí)現(xiàn)中其鄰接點(diǎn)亦先被訪問，所以在算法的實(shí)現(xiàn)中需要使用一個需要使用一個隊(duì)列隊(duì)列，用來依次記住被訪問過，用來依次記住被訪問過的頂點(diǎn)。的頂點(diǎn)。n算法開始時，將初始點(diǎn)訪問后插入隊(duì)列中，算法開始時，將初始點(diǎn)訪問后插入隊(duì)列中，以后每從隊(duì)列中刪除一個元素，就依次訪問以后每從隊(duì)列中刪除一個元素，就依次訪問它的每一個未被訪問過的鄰接點(diǎn)，并令其進(jìn)它的每一個未被訪問過的鄰接點(diǎn)，并令其進(jìn)隊(duì)，這樣，當(dāng)隊(duì)列為空時，表明所有與初始隊(duì)，這樣，當(dāng)隊(duì)列為空時，表明所有與初始點(diǎn)有路徑相通的頂點(diǎn)都以訪問完畢，算法到點(diǎn)有路徑相通的頂點(diǎn)都以訪問完畢，算法到此結(jié)束。此結(jié)束。2.2.算法實(shí)現(xiàn)算法實(shí)現(xiàn):

32、 :44 bfs(int k) int i，j; initqueue(q); printf(%cn,g.vexsk); visitedk=true; enqueue(q,k); while (!empty(q) i=dequeue(q); /vi出隊(duì)出隊(duì) for(j=0;jn;j+) /依次搜索依次搜索vi的鄰接點(diǎn)的鄰接點(diǎn) if(g.arcsij=1&!visitedj) printf(“%cn”,g.vexsj); visitedj=true; enqueue(q,j); /訪問過的訪問過的vj入隊(duì)入隊(duì) /* 從從vk出發(fā)廣度優(yōu)先搜索圖出發(fā)廣度優(yōu)先搜索圖,以鄰接矩陣作存儲結(jié)構(gòu)以鄰接矩

33、陣作存儲結(jié)構(gòu)*/45 bfsl(int k) /*以鄰接表作存儲結(jié)構(gòu)以鄰接表作存儲結(jié)構(gòu)*/ int i; edgenode *p; initqueue(q); printf(%cn,glk.vertex); visitedk=true; enqueue(q,k); while (! empty(q) i=dequeue(q); p=gli.link; /取取vi的邊表頭指針的邊表頭指針 while(p!=null) if(!visitedpadjvex-1) /依次搜索依次搜索vi的的鄰接點(diǎn)鄰接點(diǎn) printf(%cn,glpadjvex-1.vertex); visitedpadjvex-1

34、=true; enqueue(q, padjvex-1); p=pnext; v5v2v3v4v1234135121524v1v2v3v4v5vertex link46477.3 對圖進(jìn)行廣度優(yōu)先搜索得到的頂點(diǎn)序列稱為對圖進(jìn)行廣度優(yōu)先搜索得到的頂點(diǎn)序列稱為：bfs序列序列，bfs序列與遍歷序列與遍歷，圖的圖的以及以及有關(guān)有關(guān)。 二者對頂點(diǎn)的搜索次序不同二者對頂點(diǎn)的搜索次序不同 兩種遍歷方法實(shí)現(xiàn)的手段不同兩種遍歷方法實(shí)現(xiàn)的手段不同注意注意 兩種遍歷方法的時間復(fù)雜度相同兩種遍歷方法的時間復(fù)雜度相同48具有兩個或兩個以上的連通分量具有兩個或兩個以上的連通分量, , 當(dāng)從某個頂點(diǎn)當(dāng)從某個頂點(diǎn)vivi開

35、始對其進(jìn)行深度或廣度優(yōu)先搜索只能遍歷包含頂點(diǎn)開始對其進(jìn)行深度或廣度優(yōu)先搜索只能遍歷包含頂點(diǎn)vivi的連的連通分量。通分量。v1v2v3v4v5具有兩個連通分量的非連通圖具有兩個連通分量的非連通圖gc1c2非連通圖的遍歷須非連通圖的遍歷須多次調(diào)用多次調(diào)用深度或廣度優(yōu)先搜索算法深度或廣度優(yōu)先搜索算法.7.349非連通圖遍歷算法描述：非連通圖遍歷算法描述： traver( ) int i; for (i=0;in;i+) visitedi=false; for (i=0;in;i+) if(!visitedi) dfs(i); 遍歷各個遍歷各個連通分量連通分量初始訪問標(biāo)初始訪問標(biāo)志志深度優(yōu)先搜索深度

36、優(yōu)先搜索遍歷非連通圖算法遍歷非連通圖算法bfsl(i);廣度優(yōu)先搜索廣度優(yōu)先搜索遍歷非連通圖算法遍歷非連通圖算法如果圖是連通的如果圖是連通的, ,則算法則算法travertraver只調(diào)用一次只調(diào)用一次dfs(dfs(或或bfs)bfs)；如果圖包含如果圖包含n n個連通分量個連通分量, ,則算法則算法travertraver調(diào)用調(diào)用n n次次dfs(dfs(或或bfs)bfs)；7.350特點(diǎn)：特點(diǎn)：a.無向連通圖的生成樹通常是不唯一的無向連通圖的生成樹通常是不唯一的b.生成樹滿足連通性且邊數(shù)最小生成樹滿足連通性且邊數(shù)最小一、生成樹一、生成樹：連通圖連通圖g的的一個極小連通子圖，如果是一個極

37、小連通子圖，如果是含有含有g(shù)的所有的頂點(diǎn)的樹，的所有的頂點(diǎn)的樹，則稱該子圖為生成樹。則稱該子圖為生成樹。v5v2v3v4v1v3v5v2v4v1v5v2v3v4v1v5v2v3v4v151無向非連通圖無向非連通圖沒有生成樹，但其各個連通分量有生成樹，各個連通沒有生成樹，但其各個連通分量有生成樹，各個連通分量的生成樹形成一個森林，稱為分量的生成樹形成一個森林，稱為無向非連通圖的生成森林無向非連通圖的生成森林。如何求無向連通圖的生成樹？如何求無向連通圖的生成樹？對左圖深度遍歷對左圖深度遍歷得到的生成樹得到的生成樹可由兩種遍歷算法求得：可由兩種遍歷算法求得：若從圖的某頂點(diǎn)出發(fā)，作一次深度優(yōu)先搜索或廣

38、度優(yōu)先若從圖的某頂點(diǎn)出發(fā)，作一次深度優(yōu)先搜索或廣度優(yōu)先搜索，可以訪問到圖中所有頂點(diǎn)，則搜索，可以訪問到圖中所有頂點(diǎn)，則遍歷遍歷時經(jīng)過的邊和時經(jīng)過的邊和圖的所有頂點(diǎn)所構(gòu)成的子圖，稱作該圖的所有頂點(diǎn)所構(gòu)成的子圖，稱作該圖的生成樹圖的生成樹。v5v2v3v4v1v5v2v3v4v152v1v2v4v5v8v3v6v7深度優(yōu)先生成樹v1v2v4v5v8v3v6v7廣度優(yōu)先生成樹53二二. 最小生成樹最小生成樹(mst:minimum spanning tree) 無向連通圖無向連通圖的生成樹通常是不唯一的，因此，的生成樹通常是不唯一的，因此，無向連通網(wǎng)無向連通網(wǎng)的的生成樹通常也是不唯一的。生成樹通常也

39、是不唯一的。 無向連通網(wǎng)生成樹的權(quán)定義無向連通網(wǎng)生成樹的權(quán)定義為生成樹各邊權(quán)值之和。為生成樹各邊權(quán)值之和。 無向連通網(wǎng)的所有生成樹中權(quán)值最小的生成樹稱為該無向連通網(wǎng)的所有生成樹中權(quán)值最小的生成樹稱為該 連通網(wǎng)的連通網(wǎng)的最小生成樹，記為最小生成樹，記為mst。7.454n網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信線路時，用圖的頂點(diǎn)表示城市，用邊在設(shè)計(jì)通信線路時，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)的權(quán)cvw表示建立城市表示建立城市v和城市和城市w之間的之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建通信線路所需的費(fèi)用，則最小生成樹就給出了建立

40、通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。 5535v2v3v4v5v18172最小生成樹最小生成樹v5v2v3v4v1w=225872v5v2v3v4v1w=133172v3v5v2v4v1w=16581256如何求無向連通網(wǎng)的最小生成樹？如何求無向連通網(wǎng)的最小生成樹？兩種常用的算法分別是：兩種常用的算法分別是：prim算法和算法和kruskal算法。算法。1.最小生成樹的最小生成樹的mst性質(zhì)。性質(zhì)。 設(shè)設(shè)g=(v,e)是一個連通網(wǎng)，是一個連通網(wǎng)，u是頂點(diǎn)集是頂點(diǎn)集v的真子集。若的真子集。若(u,v)是是g中所有一個頂點(diǎn)在中所有一個頂點(diǎn)在u中，另一個頂點(diǎn)在中，另一個頂點(diǎn)在v-u 中

41、的中的所有邊中權(quán)值最小的一條邊，則必存在一棵包含邊所有邊中權(quán)值最小的一條邊，則必存在一棵包含邊(u,v)的的最小生成樹。最小生成樹。7.4577.4prim 算法和算法和 kruskal 算法均用到了最小生成樹的算法均用到了最小生成樹的mst性質(zhì)。性質(zhì)。prim算法思想算法思想:假設(shè)假設(shè)g=(v,e)為連通網(wǎng)絡(luò)，生成的最小生成樹為為連通網(wǎng)絡(luò)，生成的最小生成樹為t=（v，te）。）。求求t（實(shí)際上是求（實(shí)際上是求te）的步驟為：）的步驟為：1）初始化：）初始化：u=u0(u0屬于屬于v)，te= ；2）在所有）在所有u屬于屬于u，v屬于屬于v-u的邊的邊(u,v) 中找一條權(quán)值最小的邊中找一條權(quán)

42、值最小的邊(u0,v0) 并入集合并入集合te，同時，同時v0并入并入u；3）如果）如果u=v，則算法結(jié)束，否則重復(fù)，則算法結(jié)束，否則重復(fù)2）。）。2. prim算法算法5812435665157352461243561532412435615324124356152451243561524512435615455124356186587.459prim算法實(shí)現(xiàn)描述：算法實(shí)現(xiàn)描述：typedef structint fromvex,endvex; float length; edge;float distnn;edge tn-1;int j,k,m,v,min,max=10000; float

43、 d; edge e; for(j=1;jn;j+) /*構(gòu)造初始邊集構(gòu)造初始邊集t0tn-2,為侯選邊集為侯選邊集*/ tj-1.fromvex=1; /*候選邊的起點(diǎn)為第一個加入樹中的頂點(diǎn)候選邊的起點(diǎn)為第一個加入樹中的頂點(diǎn)v1*/ tj-1.endvex=j+1; /*候選邊的終點(diǎn)為候選邊的終點(diǎn)為v-u中的點(diǎn)中的點(diǎn)*/ tj-1.length=dist0j; /*終點(diǎn)為終點(diǎn)為vj的候選邊長度的候選邊長度*/生成樹邊的生成樹邊的存儲結(jié)構(gòu)存儲結(jié)構(gòu)dist和和t分別存儲分別存儲無向連通網(wǎng)的帶權(quán)鄰無向連通網(wǎng)的帶權(quán)鄰接矩陣和生成樹的邊接矩陣和生成樹的邊邊的權(quán)值邊的權(quán)值60 for(k=0;kn-1;

44、k+) /*求求t中第中第k條邊條邊*/ min=max; for(j=k;jn-1;j+) /*掃描當(dāng)前侯選邊集掃描當(dāng)前侯選邊集tk到到tn-2,找最短邊找最短邊*/ if(tj.lengthmin)min=tj.length;m=j;/*記錄當(dāng)前最短候選邊的位置記錄當(dāng)前最短候選邊的位置*/ e=tm;tm=tk;tk=e; v=tk.endvex; /*tk和和tm交換后交換后,生成的樹邊生成的樹邊:t0tk*/ for(j=k+1;jn-1;j+) /*調(diào)整候選邊集邊調(diào)整候選邊集邊tk+1tn-2*/ d=disttj.endvexv; if(dtj.length)tj.length=d

45、;tj.fromvex=v; prim算法的時間復(fù)雜度為算法的時間復(fù)雜度為o(n2) 61kruskal算法思想算法思想：n設(shè)設(shè)g= (v,e)是連通網(wǎng)，令最小生成樹的初態(tài)為只有是連通網(wǎng)，令最小生成樹的初態(tài)為只有n個個頂點(diǎn)而無邊的非連通圖頂點(diǎn)而無邊的非連通圖t=(v, )，圖中每個頂點(diǎn)自成一個，圖中每個頂點(diǎn)自成一個連通分量。連通分量。n在在e中選擇權(quán)值最小的邊，若該邊依附的頂點(diǎn)落在中選擇權(quán)值最小的邊，若該邊依附的頂點(diǎn)落在t中中不同的連通分量上，則將此邊加入到不同的連通分量上，則將此邊加入到t中，否則舍去此邊中，否則舍去此邊而選擇下一條權(quán)值最小的邊。而選擇下一條權(quán)值最小的邊。n依次類推，直到依次

46、類推，直到t中所有頂點(diǎn)都在同一連通分量上為止。中所有頂點(diǎn)都在同一連通分量上為止。該連通分量即為最小生成樹。該連通分量即為最小生成樹。3. kruskal算法算法62kruskal算法產(chǎn)算法產(chǎn)生的最小生成樹生的最小生成樹 kruskal算法的初略描述：算法的初略描述： t=(v, ); while(t中所含邊數(shù)中所含邊數(shù)n-1) 從從e中選取當(dāng)前權(quán)值最小邊中選取當(dāng)前權(quán)值最小邊(u,v); 從從e中刪去邊中刪去邊(u,v); if (u,v)并入并入t之后不產(chǎn)生回路之后不產(chǎn)生回路) 將邊將邊(u,v)并入并入t中中; 35v2v3v4v5v18172v5v2v3v4v13(c)1(a)7(d)2(

47、b)6364 7.5 最最 短短 路路 徑徑兩頂點(diǎn)之間路徑的長度：兩頂點(diǎn)之間路徑的長度：定義為路徑上各邊權(quán)值之和。定義為路徑上各邊權(quán)值之和。兩點(diǎn)間最短路徑：兩點(diǎn)間最短路徑：指的是帶權(quán)圖中，兩頂點(diǎn)之間所有路徑中指的是帶權(quán)圖中，兩頂點(diǎn)之間所有路徑中長度最小的路徑。長度最小的路徑。考慮到實(shí)際問題的有向性，將路徑上的第一個頂點(diǎn)稱為考慮到實(shí)際問題的有向性，將路徑上的第一個頂點(diǎn)稱為源點(diǎn)源點(diǎn)(source)(source)，最后一個頂點(diǎn)稱為，最后一個頂點(diǎn)稱為終點(diǎn)終點(diǎn)(destination)(destination)。并為了敘。并為了敘述方便，把源點(diǎn)述方便，把源點(diǎn)v v到終點(diǎn)到終點(diǎn)w w的最短路徑簡稱為頂點(diǎn)

48、的最短路徑簡稱為頂點(diǎn)w w的路徑。的路徑。1、定義、定義7.5657.5.1 7.5.1 單源最短路徑單源最短路徑一、定義：一、定義：對給定的有向網(wǎng)對給定的有向網(wǎng)g=(v,e)和源點(diǎn)和源點(diǎn)v，求源點(diǎn)，求源點(diǎn)v到到g中其余各頂點(diǎn)中其余各頂點(diǎn)的最短路徑的最短路徑。首先直觀地看一下如下有向網(wǎng)及源點(diǎn)首先直觀地看一下如下有向網(wǎng)及源點(diǎn)v1的單源最短路徑。的單源最短路徑。7.5源點(diǎn)源點(diǎn) 中間點(diǎn)中間點(diǎn) 終點(diǎn)終點(diǎn) 路徑長度路徑長度 1 2 10 1 4 30 1 4 3 50 1 4,3 5 60路徑長度是遞增路徑長度是遞增結(jié)論：結(jié)論：當(dāng)按長度增長的順序當(dāng)按長度增長的順序求源點(diǎn)到各頂點(diǎn)的最短路徑求源點(diǎn)到各頂點(diǎn)的

49、最短路徑時，中間點(diǎn)的最短路徑在求時，中間點(diǎn)的最短路徑在求該點(diǎn)最短路徑之前已經(jīng)求出。該點(diǎn)最短路徑之前已經(jīng)求出。1101005030106020253466二、對給定的有向網(wǎng)二、對給定的有向網(wǎng)g=(v,e)和源點(diǎn)和源點(diǎn)v，如何求單源最，如何求單源最短路徑？短路徑？dijkstra算法算法1、dijkstra算法思想：算法思想：從給定的源點(diǎn)開始，按路徑長度遞增的順序，逐從給定的源點(diǎn)開始，按路徑長度遞增的順序，逐步產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。步產(chǎn)生源點(diǎn)到其余各頂點(diǎn)的最短路徑。7.5671) 基本原理基本原理：設(shè)置一個頂點(diǎn)集合設(shè)置一個頂點(diǎn)集合s，s中的所有頂點(diǎn)其最短路徑已經(jīng)中的所有頂點(diǎn)其最短路徑已經(jīng)

50、求出，求出，初始時初始時s=v，則尚未求出最短路徑的頂點(diǎn)集為，則尚未求出最短路徑的頂點(diǎn)集為v-s。另外，設(shè)。另外，設(shè)置一個置一個數(shù)組數(shù)組d ，若頂點(diǎn)，若頂點(diǎn)vi的最短路徑已求出，則的最短路徑已求出，則di存放的是最短路存放的是最短路徑長度，否則徑長度，否則di存放的是從頂點(diǎn)存放的是從頂點(diǎn)v經(jīng)經(jīng)s 中的頂點(diǎn)到中的頂點(diǎn)到vi的所有路徑中最短的所有路徑中最短路徑的長度，路徑的長度，并稱其為并稱其為vi的距離的距離。初始時。初始時 wi 若若為為g中的邊中的邊 di= 若若不是不是g中的邊中的邊7.5設(shè)設(shè) vj 為為 v-s 中距離最短的頂點(diǎn)，可以證明中距離最短的頂點(diǎn)，可以證明（1）dj為為vj的最短

51、路徑的長度；的最短路徑的長度；（2）頂點(diǎn)）頂點(diǎn)vj為為v-s中最短路徑長度最短的頂點(diǎn)。中最短路徑長度最短的頂點(diǎn)。2、算法思想的具體實(shí)現(xiàn)、算法思想的具體實(shí)現(xiàn)：68udj為為vj的最短路徑的長度的最短路徑的長度證明：證明：若若dj不是不是vj的最短路徑長度，則從源點(diǎn)的最短路徑長度，則從源點(diǎn)v到頂點(diǎn)到頂點(diǎn)vj必存在另外一條路徑必存在另外一條路徑p，其長度小于其長度小于dj。由距離的定義可知路徑。由距離的定義可知路徑p必包含一個或多個屬于必包含一個或多個屬于v-s的中間頂點(diǎn)，的中間頂點(diǎn)，設(shè)第一個這樣的頂點(diǎn)為設(shè)第一個這樣的頂點(diǎn)為vk，v沿路徑沿路徑p到到vk的路徑長度為的路徑長度為d1， vk沿路徑沿路

52、徑p到到vj的的路徑長度為路徑長度為d2,則則p的長度為的長度為d1+d2，d1+d2dj。因?yàn)橐驗(yàn)閐k=0，所以，所以dk=d1+d2dj，而，而dk=dj；2）若）若pi除經(jīng)過除經(jīng)過s中的頂點(diǎn)外，還經(jīng)過中的頂點(diǎn)外，還經(jīng)過v-s中的中間頂點(diǎn)，設(shè)中的中間頂點(diǎn)，設(shè)vk為為v-s中第一中第一個這樣的中間頂點(diǎn)，顯然個這樣的中間頂點(diǎn)，顯然pi的長度為的長度為dk加上加上vk至至vi這段路徑的長度這段路徑的長度d，因，因?yàn)闉閐k=dj，而，而vk至至vi這段路徑的長度這段路徑的長度d=0，所以，所以pi的長度的長度=dj。由此。由此可知可知v-s中任一頂點(diǎn)的最短路徑長度均大于等于中任一頂點(diǎn)的最短路徑長度

53、均大于等于vj的最短路徑長度。的最短路徑長度。結(jié)論：經(jīng)上述兩點(diǎn)的證明可知，在求單源最短路徑的過程結(jié)論：經(jīng)上述兩點(diǎn)的證明可知，在求單源最短路徑的過程中當(dāng)頂點(diǎn)集中當(dāng)頂點(diǎn)集s一定時，可從一定時，可從v-s中選取距離最短的頂點(diǎn)，將中選取距離最短的頂點(diǎn)，將其擴(kuò)充到其擴(kuò)充到s中，且該頂點(diǎn)的距離即為其最短路徑長度。中，且該頂點(diǎn)的距離即為其最短路徑長度。702）提出問題：）提出問題：當(dāng)從當(dāng)從v-s中選取距離最短的頂點(diǎn)，將其擴(kuò)充中選取距離最短的頂點(diǎn)，將其擴(kuò)充到到s中之后，中之后，v-s中頂點(diǎn)的中頂點(diǎn)的d值可能會發(fā)生變化，因此需值可能會發(fā)生變化，因此需對對v-s中各頂點(diǎn)的中各頂點(diǎn)的d值進(jìn)行調(diào)整。值進(jìn)行調(diào)整。如何調(diào)

54、整？如何調(diào)整？7.52、算法思想的具體實(shí)現(xiàn)、算法思想的具體實(shí)現(xiàn)：71證明：證明：設(shè)設(shè)v-s中任一頂點(diǎn)中任一頂點(diǎn)vj的距離因的距離因vk加入到加入到s中而發(fā)生了變化，但其新的中而發(fā)生了變化，但其新的距離不為距離不為dk+，則必存在一條從，則必存在一條從v經(jīng)頂點(diǎn)經(jīng)頂點(diǎn)vk、vx到到vj的路徑，其長的路徑，其長度度dj小于小于vj的原來距離的原來距離dj。若。若vk到到vx 、vx到到vj的路徑長度分別為的路徑長度分別為d1和和d2,由于由于vx先于先于vk加入到加入到s中，所以中，所以dx=dk,則則dx+d2=dk+d1+d2=dj，而，而vj的原來距離的原來距離dj=dx+d2,因此因此dj=

55、dk+d1+d2=dj，與假設(shè)矛盾。所以，與假設(shè)矛盾。所以vj的新的距離值的新的距離值dj 為為dk+。7.5vvkvxvj此段長度為此段長度為d1此段長度為此段長度為d272結(jié)論：結(jié)論：由此得到了因新的頂點(diǎn)由此得到了因新的頂點(diǎn)vk加入到加入到s中之后對中之后對v-s中各頂點(diǎn)距離進(jìn)中各頂點(diǎn)距離進(jìn)行調(diào)整的方法，即：行調(diào)整的方法，即：對對v-s中任意頂點(diǎn)中任意頂點(diǎn)vj，若，若djdk+,則將則將dk+的值賦給的值賦給dj,否則，否則，dj的值不變。的值不變。3）djkstra算法的粗略描述：算法的粗略描述： s=v; /*初始化初始化v-s中各頂點(diǎn)的距離值中各頂點(diǎn)的距離值*/ while(s中的頂

56、點(diǎn)數(shù)中的頂點(diǎn)數(shù)n) 從從v-s中選取距離值最小的頂點(diǎn)中選取距離值最小的頂點(diǎn)vj; s=s+vj; 調(diào)整調(diào)整v-s中各頂點(diǎn)的距離值；中各頂點(diǎn)的距離值； 734)djkstra算法的詳細(xì)描述：算法的詳細(xì)描述： float dn;/*存放各頂點(diǎn)的距離值存放各頂點(diǎn)的距離值*/ int pn,sn;/*pn為路徑向量為路徑向量,pi記錄從源點(diǎn)到達(dá)記錄從源點(diǎn)到達(dá)i+1點(diǎn)的最短路徑上點(diǎn)的最短路徑上 該點(diǎn)的前趨頂點(diǎn)該點(diǎn)的前趨頂點(diǎn),sn為最短路徑均已求出的頂點(diǎn)集合為最短路徑均已求出的頂點(diǎn)集合*/ djkstra(c,v) float c n;/*c為有向網(wǎng)絡(luò)的帶權(quán)鄰接距陣為有向網(wǎng)絡(luò)的帶權(quán)鄰接距陣*/ int v

57、; int i,j,k,v1,pre; int min,max=200,inf=300; v1=v-1; for(i=0;in;i+) di=cv1i; if (di!=max) pi=v else pi=0; for(i=0;in;i+) si=0; sv1=1;dv1=0; for(i=0;imax*/ for(j=0;jn;j+) /*在當(dāng)前在當(dāng)前v-s集中選距離值最小的頂點(diǎn)集中選距離值最小的頂點(diǎn)*/ 初始化距離數(shù)組初始化距離數(shù)組d和記錄頂和記錄頂點(diǎn)最短路徑上該頂點(diǎn)直接前點(diǎn)最短路徑上該頂點(diǎn)直接前趨頂點(diǎn)序號的數(shù)組。趨頂點(diǎn)序號的數(shù)組。s集合賦初值集合賦初值74 if (!sj &(d

58、jmin) min=dj;k=j; sk=1; for(j=0;jdk+ckj) dj=dk+ckj;/*修改修改v-s集合中頂點(diǎn)集合中頂點(diǎn)j的距離的距離*/ pj=k+1;/*k+1是是j+1的前趨的前趨*/ for (i=0;in;i+) printf(“n%ft%d”,di,i+1); pre=pi;/*繼續(xù)找前趨頂點(diǎn)繼續(xù)找前趨頂點(diǎn)*/ while (pre!=0) printf(-%d,pre);pre=ppre-1; printf(“n”); 求求v-s中距離最短的頂點(diǎn)中距離最短的頂點(diǎn)并將該頂點(diǎn)放入集合并將該頂點(diǎn)放入集合s中中調(diào)整調(diào)整v-s頂點(diǎn)的距離頂點(diǎn)的距離輸出各頂點(diǎn)最短輸出各頂點(diǎn)

59、最短路徑長度和軌跡路徑長度和軌跡djkstra算法的時間復(fù)雜度為算法的時間復(fù)雜度為o(n2)，空間復(fù)雜度為，空間復(fù)雜度為o(n)。75打印輸出的結(jié)果為打印輸出的結(jié)果為:max1max2203-404305-3-415234101003050106020循環(huán)循環(huán)s集合集合初始化初始化k+1d0.d4p0.p412344-max max 20 0 60max max 20 0 30max max 20 0 30max max 20 0 30max max 20 0 30 0 0 4 0 4 0 0 4 0 3 0 0 4 0 3 0 0 4 0 3 0 0 4 0 34,34,3,54,3,5,1

60、4,3,5,1,2532176777.5.2 7.5.2 所有頂點(diǎn)對之間的最短路徑所有頂點(diǎn)對之間的最短路徑1.定義：定義：所有頂點(diǎn)對之間的最短路徑問題指的是：對給定的所有頂點(diǎn)對之間的最短路徑問題指的是：對給定的有向網(wǎng)有向網(wǎng)g=(v,e)，求，求g中每一對頂點(diǎn)之間的最短路徑。中每一對頂點(diǎn)之間的最短路徑。2.解決方法：解決方法：方法一：方法一：每次以一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行每次以一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行djkstradjkstra算法算法n n次。這樣可求得每一對頂點(diǎn)之間的最短路徑?？偟膱?zhí)行時次。這樣可求得每一對頂點(diǎn)之間的最短路徑。總的執(zhí)行時間為間為o(no(n3 3) )。方法二：方法二：是采用是采用floydfloyd算法，該算法的時間復(fù)雜度也是算法，該算法的時間復(fù)雜度也是o(no(n3 3) ) ，但形式上簡單些。，但形式上簡單些。7.578 假設(shè)有向網(wǎng)采用鄰接矩陣假設(shè)有向網(wǎng)采用鄰接