第七章圖PPT課件

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

2、邊又稱為弧弧，vi為為弧尾弧尾，vj為為弧頭弧頭.v(g)=v1,v2,v3,v4,v5e(g )=,7.1v 有向圖有向圖: :圖圖g g中的每一條邊都是有方向的中的每一條邊都是有方向的。v2v3v4v5v14v無向圖無向圖: 圖中的每一條邊都是無方向的。圖中的每一條邊都是無方向的。一條邊為兩個頂點的無序?qū)σ粭l邊為兩個頂點的無序?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) 是是一條無向邊，則稱頂點一條無向邊，則稱頂點 vi 和和 vj 互為互為鄰接點鄰接點(adjacent)，(vi,vj) 與頂點與頂點 vi 和和 vj 相關(guān)聯(lián)相關(guān)聯(lián)(incident)。v若若 是一條有向邊，則稱頂點是一條有向邊，則稱頂點 vi 鄰接到鄰接到 vj，頂點，頂點 vj 鄰鄰接于接于vi， 與頂點與頂點 vi 和和 vj 相關(guān)聯(lián)。相關(guān)聯(lián)。v無向完全圖無向完全圖任何兩個頂點之間都有邊的無向圖。共有任何兩個頂點之間都有邊的無向圖。共有 n(n-1)/2 條邊。條邊。v有向完全圖有向完全圖任何兩個頂點

4、之對間都有弧的有向圖。共有任何兩個頂點之對間都有弧的有向圖。共有n(n-1)條邊。條邊。無向完全圖無向完全圖有向完全圖有向完全圖67.1度、入度和出度的概念：度、入度和出度的概念： 無向圖中無向圖中頂點頂點v的度的度為關(guān)聯(lián)于該頂點的邊的數(shù)目，記為為關(guān)聯(lián)于該頂點的邊的數(shù)目，記為d(v)有向圖中把以頂點有向圖中把以頂點v為終點的邊的數(shù)目稱為為終點的邊的數(shù)目稱為v的的入度入度，記為，記為id(v) 把以頂點把以頂點v為始點的邊的數(shù)目稱為為始點的邊的數(shù)目稱為v的的出度出度,記為記為od(v) 頂點的度頂點的度定義為入度與出度之和，即定義為入度與出度之和，即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無論有向圖還是無向圖，頂點數(shù)無論有向圖還是無向圖，頂點數(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)的頂點均在中的邊所關(guān)聯(lián)的頂點均在v中中，則，則g=(v,e)也是一個圖，并稱其為也是一

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

7、 v2v3v4v5v1該有向圖中頂點該有向圖中頂點v2到頂點到頂點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簡單路徑簡單路徑：除起點和終點外，其余頂點均不相同的路徑稱：除起點和終點外，其余頂點均不相同的路徑稱為為簡單路徑簡單路徑。起點和終點相同的簡單路徑稱為。起點和終點相同的簡單路徑稱為簡單回

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

9、向圖無向圖g g中，若任意兩個頂點間存在路徑中，若任意兩個頂點間存在路徑( (即連通的即連通的),),則稱則稱g g為為連通圖連通圖。v無向圖無向圖g g的極大連通子圖稱為的極大連通子圖稱為g g的的連通分量連通分量。v1v2v3v4v5非連通圖非連通圖g的兩個連通分量的兩個連通分量強連通圖只有強連通圖只有一個一個強連通分量強連通分量非強連通圖有非強連通圖有多個多個強連通分量強連通分量12注意：注意：帶權(quán)圖中權(quán)值的含義視具體問題而定帶權(quán)圖中權(quán)值的含義視具體問題而定(距離、耗費等距離、耗費等).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 圖的存儲涉及到兩方面：頂點內(nèi)容的存儲和邊圖的存儲涉及到兩方面：頂點內(nèi)容的存儲和邊( (邏輯邏輯關(guān)系關(guān)系) )的存儲。圖的存儲所采用的兩種常用方法為：的存儲。圖的存儲所采用的兩種常用方法為：鄰接鄰接矩陣矩陣和和鄰接表鄰接表。7.2.1 7.2.1 鄰接矩陣表示法鄰接矩陣表示法7.2 7.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)1.鄰接矩陣定義鄰接矩陣定義鄰接矩陣鄰接矩陣指的是表示圖中頂點之間相鄰關(guān)系的矩陣。指的是表示圖中頂點之間相鄰關(guān)系的矩陣。7.214設(shè)設(shè)g=(v,e)是具有是具有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 . /* 圖中頂點個數(shù)圖中頂點個數(shù) */ #define e . /* 圖中邊圖中邊(弧弧)條數(shù)條數(shù) */ typedef

13、 char vextype; /* 頂點數(shù)據(jù)類型頂點數(shù)據(jù)類型 */ typedef float adjtype; /* 權(quán)值類型權(quán)值類型 */ typedef struct vextype vexsn; /* 數(shù)組數(shù)組vexs 用于存儲頂點數(shù)據(jù)用于存儲頂點數(shù)據(jù) */ adjtype arcsnn; /* arcs 為鄰接矩陣為鄰接矩陣 */ graph; 若圖中頂點信息僅為編號若圖中頂點信息僅為編號, 則僅需存儲一個鄰接矩陣即可表示圖。則僅需存儲一個鄰接矩陣即可表示圖。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; /*因為是無向網(wǎng)因為是無向網(wǎng)*/ ga arcsj-1i-1=w; 建立一個采用鄰接矩陣表示法實現(xiàn)存儲的建立一個采用鄰接矩陣表示法實現(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該算法的時間復雜度為該算法的時間復雜度為 o(n+n2+e) , 因為因為 en2 ,所以為所以為 o(n2)19 adjvex next7.2.2 7.2.2 鄰接表表示法鄰接表表示法 鄰接表表示法類似于樹的孩子鏈表表示法。對于圖鄰接表表示法類似于樹的孩子鏈表表示法。對于圖g g中

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

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

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

19、xlink頂點域頂點域 指針域指針域7.2vexnode gan;23鄰鄰接接表表vexnode ga25；vexnode ga14；7.2v3v1v2v4v5v1v4v2v34 21 1 1332 2 v1v2v3v4vertexlink4 頂點表頂點表邊表邊表5 4 2 1vertex linkv1v2v3v4v51 2 1 4 頂點表頂點表出邊表出邊表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é)點生成邊表結(jié)點 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+)/*讀入頂點信息并初始化邊表頭指針讀入頂點信息并初始化邊表頭指針*/ gai.vertex=getchar( );gai.link=null; for(k=0;ke;k+) 生成無向圖的時間復雜度是生成無向圖的時間復雜度是o(n+e)o(n+e) 生成有向圖的時間復雜度是生成有向圖的時間復雜度是o(n+e)o(n+e)25(1) 一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一個圖

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

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

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

25、 v4 - v8 - v5 - v3 - v6 - v7特點：遍歷過程中盡可能地先對縱深方向進行搜索特點：遍歷過程中盡可能地先對縱深方向進行搜索v1v2v4v5v6v3v7v8fffff 假設(shè)從假設(shè)從v1開始出發(fā)進行遍歷開始出發(fā)進行遍歷: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的未曾訪問過的鄰接點出的未曾訪問過的鄰接點出 發(fā)進行深度優(yōu)先搜索發(fā)進行深度優(yōu)先搜索*/ dfsl(p-adjvex-1); p=p-next; /*找找vi的下一鄰接點的下一鄰接點*/3839 對圖進行深度優(yōu)先搜索得到的頂點序列稱為對圖進行深度優(yōu)先搜索得到的頂點序列稱為注意注意7.3dfs序列序列不唯一，不唯一，它與遍歷它與遍歷算法，算法，圖的圖的存存儲結(jié)構(gòu)儲結(jié)構(gòu)以及以及初始出發(fā)點初始出發(fā)點有關(guān)有關(guān)。3.3.算法分析算法分析對于

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

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

31、的頂點，其鄰接點亦先被訪問，所以在算法的實現(xiàn)中其鄰接點亦先被訪問，所以在算法的實現(xiàn)中需要使用一個需要使用一個隊列隊列，用來依次記住被訪問過，用來依次記住被訪問過的頂點。的頂點。n算法開始時，將初始點訪問后插入隊列中，算法開始時，將初始點訪問后插入隊列中，以后每從隊列中刪除一個元素，就依次訪問以后每從隊列中刪除一個元素，就依次訪問它的每一個未被訪問過的鄰接點，并令其進它的每一個未被訪問過的鄰接點，并令其進隊，這樣，當隊列為空時，表明所有與初始隊，這樣，當隊列為空時，表明所有與初始點有路徑相通的頂點都以訪問完畢，算法到點有路徑相通的頂點都以訪問完畢，算法到此結(jié)束。此結(jié)束。2.2.算法實現(xiàn)算法實現(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出隊出隊 for(j=0;jn;j+) /依次搜索依次搜索vi的鄰接點的鄰接點 if(g.arcsij=1&!visitedj) printf(“%cn”,g.vexsj); visitedj=true; enqueue(q,j); /訪問過的訪問過的vj入隊入隊 /* 從從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的的鄰接點鄰接點 printf(%cn,glpadjvex-1.vertex); visitedpadjvex-1

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

35、始對其進行深度或廣度優(yōu)先搜索只能遍歷包含頂點開始對其進行深度或廣度優(yōu)先搜索只能遍歷包含頂點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); 遍歷各個遍歷各個連通分量連通分量初始訪問標初始訪問標志志深度優(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特點：特點：a.無向連通圖的生成樹通常是不唯一的無向連通圖的生成樹通常是不唯一的b.生成樹滿足連通性且邊數(shù)最小生成樹滿足連通性且邊數(shù)最小一、生成樹一、生成樹：連通圖連通圖g的的一個極小連通子圖，如果是一個極

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

38、度優(yōu)先若從圖的某頂點出發(fā)，作一次深度優(yōu)先搜索或廣度優(yōu)先搜索，可以訪問到圖中所有頂點，則搜索，可以訪問到圖中所有頂點，則遍歷遍歷時經(jīng)過的邊和時經(jīng)過的邊和圖的所有頂點所構(gòu)成的子圖，稱作該圖的所有頂點所構(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ò)的最小生成樹在實際中有廣泛應(yīng)用。例如，網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。例如，在設(shè)計通信線路時，用圖的頂點表示城市，用邊在設(shè)計通信線路時，用圖的頂點表示城市，用邊(v,w)的權(quán)的權(quán)cvw表示建立城市表示建立城市v和城市和城市w之間的之間的通信線路所需的費用，則最小生成樹就給出了建通信線路所需的費用，則最小生成樹就給出了建立

40、通信網(wǎng)絡(luò)的最經(jīng)濟的方案。立通信網(wǎng)絡(luò)的最經(jīng)濟的方案。 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是頂點集是頂點集v的真子集。若的真子集。若(u,v)是是g中所有一個頂點在中所有一個頂點在u中，另一個頂點在中，另一個頂點在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（實際上是求（實際上是求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é)束，否則重復，則算法結(jié)束，否則重復2）。）。2. prim算法算法5812435665157352461243561532412435615324124356152451243561524512435615455124356186587.459prim算法實現(xiàn)描述：算法實現(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; /*候選邊的起點為第一個加入樹中的頂點候選邊的起點為第一個加入樹中的頂點v1*/ tj-1.endvex=j+1; /*候選邊的終點為候選邊的終點為v-u中的點中的點*/ tj-1.length=dist0j; /*終點為終點為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+) /*掃描當前侯選邊集掃描當前侯選邊集tk到到tn-2,找最短邊找最短邊*/ if(tj.lengthmin)min=tj.length;m=j;/*記錄當前最短候選邊的位置記錄當前最短候選邊的位置*/ 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算法的時間復雜度為算法的時間復雜度為o(n2) 61kruskal算法思想算法思想：n設(shè)設(shè)g= (v,e)是連通網(wǎng)，令最小生成樹的初態(tài)為只有是連通網(wǎng)，令最小生成樹的初態(tài)為只有n個個頂點而無邊的非連通圖頂點而無邊的非連通圖t=(v, )，圖中每個頂點自成一個，圖中每個頂點自成一個連通分量。連通分量。n在在e中選擇權(quán)值最小的邊，若該邊依附的頂點落在中選擇權(quán)值最小的邊，若該邊依附的頂點落在t中中不同的連通分量上，則將此邊加入到不同的連通分量上，則將此邊加入到t中，否則舍去此邊中，否則舍去此邊而選擇下一條權(quán)值最小的邊。而選擇下一條權(quán)值最小的邊。n依次類推，直到依次

46、類推，直到t中所有頂點都在同一連通分量上為止。中所有頂點都在同一連通分量上為止。該連通分量即為最小生成樹。該連通分量即為最小生成樹。3. kruskal算法算法62kruskal算法產(chǎn)算法產(chǎn)生的最小生成樹生的最小生成樹 kruskal算法的初略描述：算法的初略描述： t=(v, ); while(t中所含邊數(shù)中所含邊數(shù)n-1) 從從e中選取當前權(quán)值最小邊中選取當前權(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 最最 短短 路路 徑徑兩頂點之間路徑的長度：兩頂點之間路徑的長度：定義為路徑上各邊權(quán)值之和。定義為路徑上各邊權(quán)值之和。兩點間最短路徑：兩點間最短路徑：指的是帶權(quán)圖中，兩頂點之間所有路徑中指的是帶權(quán)圖中，兩頂點之間所有路徑中長度最小的路徑。長度最小的路徑?？紤]到實際問題的有向性，將路徑上的第一個頂點稱為考慮到實際問題的有向性，將路徑上的第一個頂點稱為源點源點(source)(source)，最后一個頂點稱為，最后一個頂點稱為終點終點(destination)(destination)。并為了敘。并為了敘述方便，把源點述方便，把源點v v到終點到終點w w的最短路徑簡稱為頂點

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

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

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

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

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

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

54、整？如何調(diào)整？7.52、算法思想的具體實現(xiàn)、算法思想的具體實現(xiàn)：71證明：證明：設(shè)設(shè)v-s中任一頂點中任一頂點vj的距離因的距離因vk加入到加入到s中而發(fā)生了變化，但其新的中而發(fā)生了變化，但其新的距離不為距離不為dk+，則必存在一條從，則必存在一條從v經(jīng)頂點經(jīng)頂點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é)論：由此得到了因新的頂點由此得到了因新的頂點vk加入到加入到s中之后對中之后對v-s中各頂點距離進中各頂點距離進行調(diào)整的方法，即：行調(diào)整的方法，即：對對v-s中任意頂點中任意頂點vj，若，若djdk+,則將則將dk+的值賦給的值賦給dj,否則，否則，dj的值不變。的值不變。3）djkstra算法的粗略描述：算法的粗略描述： s=v; /*初始化初始化v-s中各頂點的距離值中各頂點的距離值*/ while(s中的頂

56、點數(shù)中的頂點數(shù)n) 從從v-s中選取距離值最小的頂點中選取距離值最小的頂點vj; s=s+vj; 調(diào)整調(diào)整v-s中各頂點的距離值；中各頂點的距離值； 734)djkstra算法的詳細描述：算法的詳細描述： float dn;/*存放各頂點的距離值存放各頂點的距離值*/ int pn,sn;/*pn為路徑向量為路徑向量,pi記錄從源點到達記錄從源點到達i+1點的最短路徑上點的最短路徑上 該點的前趨頂點該點的前趨頂點,sn為最短路徑均已求出的頂點集合為最短路徑均已求出的頂點集合*/ 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+) /*在當前在當前v-s集中選距離值最小的頂點集中選距離值最小的頂點*/ 初始化距離數(shù)組初始化距離數(shù)組d和記錄頂和記錄頂點最短路徑上該頂點直接前點最短路徑上該頂點直接前趨頂點序號的數(shù)組。趨頂點序號的數(shù)組。s集合賦初值集合賦初值74 if (!sj &(d

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

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