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

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

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

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

4、(n-1)/2,則該有向圖為完全無向圖有向圖：頂點數(shù)n和邊數(shù)e滿足0≦e≦n(n-1)。如果 e=n(n-1)，則該圖為完全有向圖如果e<nlogn,則該圖為稀疏圖。,完全無向圖：e=5*4/2=10,完全有向圖：e=5*4=20,,子圖,設(shè)有兩個圖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）是一條無向邊，則稱vi 和vj互為鄰接點（Adjacent)，或稱vi 與vj 相鄰接；并稱邊（vi，vj）依附或關(guān)聯(lián)（Incident)于頂點vi 和vj ，或稱邊（vi，vj）與頂點vi 和vj 相關(guān)聯(lián)。圖G1中，頂點0與頂點1相互鄰接，邊（0，1）與頂點0和頂點1關(guān)聯(lián)。若是一條有向邊，則稱vi 鄰接到vj ，或稱vj 鄰接于vi；并稱邊關(guān)聯(lián)于頂點vi 和vj ，或稱邊與vi 和vj 相關(guān)聯(lián)。圖G2中，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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