數(shù)據(jù)結(jié)構(gòu)與算法分析

1、數(shù)據(jù)結(jié)構(gòu)與算法分析,第六章 圖（1）,6.1. 圖的基本概念,圖的定義：圖是由頂點(diǎn)集合(vertex)及頂點(diǎn)間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph＝( V, E ) 其中，V = { x | x ∈某個(gè)數(shù)據(jù)對(duì)象} 是頂點(diǎn)的有窮非空集合； E = {(x, y) | x, y ∈ V } 或E = { | x, y ∈ V} 是頂點(diǎn)之間關(guān)系的有窮集合，也叫做邊(edge)集合。,

2、若圖G的每條邊都是沒有方向的，則稱G為無(wú)向圖（UnDigraph) ，圖中兩個(gè)頂點(diǎn)間最多只存在一條邊。無(wú)向邊用兩個(gè)頂點(diǎn)的無(wú)序?qū)Ρ硎荆洖?頂點(diǎn)x,頂點(diǎn)y）下圖為例子：V(G1) ={0,1,2,3,4}E(G1) ={(0,1),(0,2),(0,3), (0,4), (1,2), (1,3), (2,4)},無(wú)向圖G1,無(wú)向圖,有向圖,若圖G的每條邊都有方向，則稱G為有向圖（Digraph)。有向邊（即?。┯蓛蓚€(gè)頂點(diǎn)組成的有序

3、對(duì)來(lái)表示，記為 （也可稱）。舉例：V(G2)={0,1,2,3,4}E(G2)={,,,,,},有向圖G2,網(wǎng)絡(luò),若將圖中的每條邊都有一個(gè)數(shù)與之關(guān)聯(lián)，則稱該數(shù)為邊或弧的權(quán)，并稱這種帶權(quán)的圖為網(wǎng)絡(luò)(Network)。通常權(quán)是一個(gè)具有某種意義的數(shù)（如表示兩頂點(diǎn)間的距離、耗費(fèi)等）。V(G2)={0,1,2,3}E(G2)={,,,,},網(wǎng)絡(luò),邊和頂點(diǎn)之間的關(guān)系,無(wú)向圖：頂點(diǎn)數(shù)n和邊數(shù)e滿足: 0≦e≦n(n-1)/2。如果e=n

4、(n-1)/2,則該有向圖為完全無(wú)向圖有向圖：頂點(diǎn)數(shù)n和邊數(shù)e滿足0≦e≦n(n-1)。如果 e=n(n-1)，則該圖為完全有向圖如果e<nlogn,則該圖為稀疏圖。,完全無(wú)向圖：e=5*4/2=10,完全有向圖：e=5*4=20,,子圖,設(shè)有兩個(gè)圖G＝(V，E)和G′＝(V′，E′)。若V’∈V,且E′∈E，則稱圖G′是圖G的子圖。例：,,,,,,,,,,,,,0,1,2,3,4,,,,,,,,,,0,1,2,4,圖

5、G,圖G’,若（vi，vj）是一條無(wú)向邊，則稱vi 和vj互為鄰接點(diǎn)（Adjacent)，或稱vi 與vj 相鄰接；并稱邊（vi，vj）依附或關(guān)聯(lián)（Incident)于頂點(diǎn)vi 和vj ，或稱邊（vi，vj）與頂點(diǎn)vi 和vj 相關(guān)聯(lián)。圖G1中，頂點(diǎn)0與頂點(diǎn)1相互鄰接，邊（0，1）與頂點(diǎn)0和頂點(diǎn)1關(guān)聯(lián)。若是一條有向邊，則稱vi 鄰接到vj ，或稱vj 鄰接于vi；并稱邊關(guān)聯(lián)于頂點(diǎn)vi 和vj ，或稱邊與vi 和vj 相關(guān)聯(lián)。圖G2中，

6、邊∈G2，稱頂點(diǎn)4鄰接到2，邊與頂點(diǎn)4和2關(guān)聯(lián),鄰接與關(guān)聯(lián),無(wú)向圖G1,有向圖G2,度,無(wú)向圖中頂點(diǎn)v 的度（Degree）是關(guān)聯(lián)于該頂點(diǎn)的邊的數(shù)目，或與該頂點(diǎn)相鄰的頂點(diǎn)數(shù)目，記為D（v）。若G 是有向圖，則把鄰接到頂點(diǎn)v 的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v 的入度（Indegree），記為ID（v）；把鄰接于頂點(diǎn)v 的頂點(diǎn)數(shù)目或邊數(shù)目稱為頂點(diǎn)v 的出度（Outdegree），記為OD（v）；頂點(diǎn)v 的度則定義為該頂點(diǎn)的入度和出度之和，即D

7、（v）= ID（v）+ OD（v）無(wú)論是有向圖還是無(wú)向圖，頂點(diǎn)數(shù)n 、邊數(shù)e 和度數(shù)之間的關(guān)系為： e = Σni=0D( v i )/2,路徑,在無(wú)向圖G 中，若存在一個(gè)頂點(diǎn)序列vp ,vi1 , vi2 , …vim ,vq，使得 （vp ,vi1）,（vi1 ,vi2）, …,（vim ,vq ）∈E(G)，則稱頂點(diǎn)序列（vp ,vi1）,（vi1 ,vi2）, …,（vim ,v

8、q ）∈E(G) 為從vp到vq的一條（Path）。在有向圖G 中，若存在一個(gè)頂點(diǎn)序列vp ,vi1 , vi2 , …vim ,vq，使得有向邊, , …,∈E(G)，則稱頂點(diǎn)vp路到vq有一條有向路徑（Path）。無(wú)權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條數(shù)。有權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。簡(jiǎn)單路徑：若路徑上各頂點(diǎn)vp ,vi1 , vi2 , …vim ,vq均不互相同, 則稱這樣的路徑為簡(jiǎn)單路徑。環(huán)：若簡(jiǎn)單路徑長(zhǎng)度大于

9、2，且第一個(gè)頂點(diǎn)v1 與最后一個(gè)頂點(diǎn)vm 重合, 則稱這樣的簡(jiǎn)單路徑為回路或環(huán)。,根,在一個(gè)有向圖中，若存在一個(gè)頂點(diǎn)v，從該頂點(diǎn)有路徑可達(dá)到圖中所有的其它頂點(diǎn)，則稱這個(gè)圖為有根圖，v為該圖的根圖G中，頂點(diǎn)0為根。,,,,,,,,,,,,,0,1,2,3,4,圖G 有向圖,圖的連通性,在無(wú)向圖中, 若從頂點(diǎn)vi到頂點(diǎn)vj有路徑, 則稱頂點(diǎn)vi與vj是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱此圖是連通圖。否則為非聯(lián)通圖。非連

10、通圖的極大連通子圖叫做連通分量。,無(wú)向圖G,G的連通分量,,,,,0,1,2,,6,,5,,,是連通分量嗎？,強(qiáng)連通,在有向圖中, 若一對(duì)頂點(diǎn)vi和vj存在一條從vi到vj和從vj到vi的路徑, 則稱vi和vj是強(qiáng)連通的。若有向圖中任意兩個(gè)頂點(diǎn)都是強(qiáng)連通的，則稱該圖為強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為圖的強(qiáng)連通分量 例：,B,C,A,,,,D,,B,C,A,,,,強(qiáng)連通圖,B,A,,,A、B強(qiáng)連通,圖G的兩個(gè)強(qiáng)連通分量,B,C,

11、A,,,,D,圖G,6.2 圖的存儲(chǔ)方法,圖的結(jié)構(gòu)復(fù)雜，不確定性很強(qiáng)圖的存儲(chǔ)方法很多，我們主要學(xué)習(xí)鄰接矩陣法和鄰接表法,鄰接矩陣法概念,設(shè)G=（V，E）是有n個(gè)頂點(diǎn)的圖，在圖的鄰接矩陣表示法中，可用兩個(gè)表格分別存儲(chǔ)數(shù)據(jù)元素（頂點(diǎn)）的信息和數(shù)據(jù)元素之間的關(guān)聯(lián)（邊）信息。通常用一維數(shù)組（順序表）存儲(chǔ)數(shù)據(jù)元素的信息，用二維數(shù)組（鄰接矩陣）存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系。此二維數(shù)組又稱鄰接矩陣。鄰接矩陣存儲(chǔ)方式可用于無(wú)向圖或有向圖。無(wú)向圖的鄰接矩

12、陣是對(duì)稱的，有向圖的鄰接矩陣可能是不對(duì)稱的。,,設(shè)無(wú)向圖G=(V,E)是一個(gè)有n個(gè)頂點(diǎn)的圖，則圖的鄰接矩陣A是n階方陣，其內(nèi)容如下：,圖的鄰接矩陣,網(wǎng)絡(luò)的鄰接矩陣,對(duì)于含權(quán)的網(wǎng)絡(luò)而言，其鄰接矩陣可定義如下：其中W(i, j)是與邊或弧相關(guān)的權(quán)。,例子,鄰接矩陣的特點(diǎn),無(wú)向圖的鄰接矩陣是對(duì)稱的，因?yàn)槿簦╲i，vj）∈ E，則必有（vj，vi）∈ E；有向圖的鄰接矩陣則不一定對(duì)稱，因?yàn)槿簟?E，卻但不一定有∈ E。無(wú)向圖的鄰接

13、矩陣可采用上三角或下三角矩陣進(jìn)行壓縮存儲(chǔ)，其存儲(chǔ)空間只需n（n+1）/2，。有向圖的鄰接矩陣所需存儲(chǔ)空間為n2。,頂點(diǎn)的度數(shù),用鄰接矩陣表示圖，很容易判定任意兩個(gè)頂點(diǎn)之間是否有邊相連，并求得各個(gè)頂點(diǎn)的度數(shù)。對(duì)于無(wú)向圖，頂點(diǎn)vi的度數(shù)是鄰接矩陣中第i行或第i列值為1的元素個(gè)數(shù)，即：D（vi）= ∑n-1j=0A(i,j)=∑n-1j=0A(j,i)對(duì)于有向圖，鄰接矩陣中第i行值為1的元素個(gè)數(shù)為頂點(diǎn)vi的出度，第i列值為1的元素的個(gè)數(shù)

14、為頂點(diǎn)vi的入度，即：OD（vi）= ∑n-1j=0A(i,j)ID（vi）= ∑n-1j=0A(j,i),#define FINITY 5000 /*此處用5000代表無(wú)窮大*/#define m 20 /*最大頂點(diǎn)數(shù)*/typedef char vertextype; /*頂點(diǎn)值類型*/typedef int edgetype; /*權(quán)值類型*/typedef struct{vertextype vexs[m];

15、/*頂點(diǎn)信息域*/edgetype edges[m][m]; /*鄰接矩陣*/int n,e; /*圖中頂點(diǎn)總數(shù)與邊數(shù)*/} mgraph; /*鄰接矩陣表示的圖類型*/,C 定義,鄰接表存儲(chǔ)形式是一種鏈?zhǔn)酱鎯?chǔ)與順序存儲(chǔ)結(jié)合的存儲(chǔ)方法。這種存儲(chǔ)方式只考慮非零頂點(diǎn)。鄰接表的存儲(chǔ)結(jié)構(gòu)分為兩級(jí)：第一級(jí)是順序結(jié)構(gòu)，存儲(chǔ)圖的頂點(diǎn)，第二級(jí)是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，存儲(chǔ)圖中每個(gè)結(jié)點(diǎn)的邊。,2．鄰接表,圖頂點(diǎn)的存儲(chǔ),單個(gè)頂點(diǎn)的存儲(chǔ)：圖中所有頂點(diǎn)的

16、存儲(chǔ)：,(a)頭結(jié)點(diǎn),圖中邊的存儲(chǔ),頂點(diǎn)所有的邊，用一個(gè)鏈表表示。鏈表的結(jié)點(diǎn)定義包括兩個(gè)域：頂點(diǎn)域：存放鄰接頂點(diǎn)指針域：存放指向另一個(gè)鄰接頂點(diǎn)的指針,(c)網(wǎng)絡(luò)的表結(jié)點(diǎn),(b)無(wú)權(quán)圖的表結(jié)點(diǎn),舉例,,,圖的鄰接表描述,typedef char VertexData; //頂點(diǎn)數(shù)據(jù)類型typedef int EdgeData; //邊上權(quán)值類型typedef struct node { //邊表結(jié)點(diǎn)int adjvex; /

17、/鄰接點(diǎn)域（下標(biāo)）EdgeData cost; //邊上的權(quán)值struct node *next; //下一邊鏈接指針} EdgeNode;typedef struct { //頂點(diǎn)表結(jié)點(diǎn)VertexData vertex; //頂點(diǎn)數(shù)據(jù)域EdgeNode * firstedge; //邊鏈表頭指針} VertexNode;typedef struct { //圖的鄰接表VertexNode vexlist

18、[NumVertices];int n, e; //圖中當(dāng)前的頂點(diǎn)個(gè)數(shù)與邊數(shù)} AdjGraph;,存儲(chǔ)效率,若無(wú)向圖中有n個(gè)頂點(diǎn)，e條邊，則它的鄰接表存儲(chǔ)結(jié)構(gòu)需要n個(gè)頭結(jié)點(diǎn)和2e個(gè)邊結(jié)點(diǎn)，在邊稀疏（e遠(yuǎn)小于<<n（n-1）/2）的情況下，用鄰接表存儲(chǔ)表示圖比鄰接矩陣表示存儲(chǔ)圖節(jié)省存儲(chǔ)空間。,三、無(wú)向圖鄰接表的構(gòu)造算法,void CreateGraph (AdjGraph G) { cin >> G.n

19、 >> G.e; //1.輸入頂點(diǎn)個(gè)數(shù)和邊數(shù)for ( int i = 0; i > G.vexlist[i].vertex; //輸入頂點(diǎn)信息G.vexlist[i].firstedge = NULL; } //邊表置為空表for ( i = 0; i > tail >> head; //輸入(變量說明省了)EdgeNode * p = new EdgeNode; //建立邊結(jié)點(diǎn)

20、p→adjvex = head; //設(shè)置邊結(jié)點(diǎn)p→next = G.vexlist[tail].firstedge; //鏈入第tail 號(hào)鏈表的前端G.vexlist[tail].firstedge = p;p = new EdgeNode;p→adjvex = tail; p→next = G.vexlist[head].firstedge; //鏈入第head 號(hào)鏈表的前端G.vexli

21、st[head].firstedge = p; }} //時(shí)間復(fù)雜度：O(2e+n),A,D,C,E,B,有向圖鄰接表的構(gòu)造算法,void CreateGraph (AdjGraph G) { cin >> G.n >> G.e; //1.輸入頂點(diǎn)個(gè)數(shù)和邊數(shù)for ( int i = 0; i > G.vexlist[i].vertex; //2.1輸入頂點(diǎn)信息G.vexlist[i].fi

22、rstedge = NULL; } //2.2邊表置為空表for ( i = 0; i > tail >> head >> weight; //輸入(變量說明省了)EdgeNode * p = new EdgeNode; //3.2建立邊結(jié)點(diǎn)p→adjvex = tail; //3.3設(shè)置邊結(jié)點(diǎn)p→next = G.vexlist[head].firstedge; //3.4鏈入第ta

23、il 號(hào)鏈表的前端G.vexlist[head].firstedge = p;}} //時(shí)間復(fù)雜度：O(e+n),網(wǎng)絡(luò)鄰接表的構(gòu)造算法,void CreateGraph (AdjGraph G) { cin >> G.n >> G.e; //1.輸入頂點(diǎn)個(gè)數(shù)和邊數(shù)for ( int i = 0; i > G.vexlist[i].vertex; //2.1輸入頂點(diǎn)信息G.vexli

24、st[i].firstedge = NULL; } //2.2邊表置為空表for ( i = 0; i > tail >> head >> weight; //輸入(變量說明省了)EdgeNode * p = new EdgeNode; //3.2建立邊結(jié)點(diǎn)p→adjvex = tail; p→cost = weight; //3.3設(shè)置邊結(jié)點(diǎn)p→next = G.vexlist

25、[head].firstedge; //3.4鏈入第tail 號(hào)鏈表的前端G.vexlist[head].firstedge = p;}} //時(shí)間復(fù)雜度：O(2e+n),空間復(fù)雜度分析,有向圖： S=O(e+n)無(wú)向圖：S= O(2e+n)當(dāng)e<<n2 時(shí)，S= O(n),兩種存儲(chǔ)結(jié)構(gòu)的比較,在鄰接矩陣中求邊的數(shù)目e ，必須檢查整個(gè)矩陣，所耗時(shí)間是O(n2) ，與邊的個(gè)數(shù)e 無(wú)關(guān)；而在鄰接表中求邊的數(shù)目e