數(shù)據(jù)結(jié)構(gòu)7圖A課件

1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容多對多（m:n)17.1 基本術(shù)語7.2 存儲結(jié)構(gòu)7.3 圖的遍歷7.4 圖的其他運算7.5 圖的應(yīng)用第7章 圖27.1 圖的基本術(shù)語圖：記為 G( V, E )，其中： V 是G的頂點集合，是有窮非空集； E 是G的邊集合，是有窮集。問：當(dāng)E(G)為空時，圖G存在否？答：還存在！但此時圖G只有頂點而沒有邊。有向圖：無向圖：完全圖：圖G1中的每條邊都是有方向的；圖G中的每條邊都是無方向的；圖G任意兩個頂點都有一條邊相連接；若 n 個頂點的無向圖有 n(n-1)/2 條邊, 稱為無向完全圖若 n 個頂點的有向圖有n(n-1) 條邊, 稱為有向完全圖稠密圖 vs. 稀疏圖v1v2

2、v3v4G1v1v2v3v5v4v4G23例：判斷下列4種圖形各屬什么類型？無向無向圖(樹)有向圖有向n(n-1)/2 條邊n(n-1) 條邊G1的頂點集合為V=0,1,2,3邊集合為E=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)完全圖完全圖4設(shè)有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。子 圖：帶權(quán)圖：即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)值（即與邊相關(guān)的數(shù)）。帶權(quán)圖網(wǎng) 絡(luò)：5鄰接點：有向邊 是G中的一條邊，則稱 u 鄰接到 v。 頂點v的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。 在有向

3、圖中, 頂點的度等于該頂點的入度與出度之和。 頂點 v 的入度是以 v 為終點的有向邊的條數(shù), 記作 ID(v); 頂點 v 的出度是以 v 為始點的有向邊的條數(shù), 記作 OD(v)。 頂點數(shù)vi和邊數(shù)e的關(guān)系：無論是有向圖還是無向圖，其邊數(shù)等于各個頂點度數(shù)總和的一半。若 (u, v) 是G中的一條邊，則稱 u 與 v 互為鄰接頂點鄰接到：度、入度和出度：v1v2v3v4G1v1v2v3v5v4v4G2TD(v1)=1+2(v1,v2)(v1,v4)TD(v1)=26簡單路徑：路徑上各頂點 v1,v2,.,vm 均不互相重復(fù)?；?路：若路徑上第一個頂點 v1 與最后一個頂點vm 重合，則稱這樣

4、的路徑為回路或環(huán)。路徑長度：非帶權(quán)圖的路徑長度是指此路徑上邊的條數(shù)；帶權(quán)圖的路徑長度是指路徑上各邊的權(quán)之和。有兩類圖形不在本章討論之列：路徑：在圖 G(V, E) 中, 若從頂點 vi 出發(fā), 沿一些邊經(jīng)過一些頂點 vp1, vp2, , vpm，到達(dá)頂點vj。則稱頂點序列 ( vi vp1 vp2 . vpm vj ) 為從頂點vi 到頂點 vj 的路徑。它經(jīng)過的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj)應(yīng)當(dāng)是G的邊(屬于E)。7小結(jié)：概念及術(shù)語圖G=(V, E)；有向邊和無向邊有向完全圖（稀疏？稠密？）、網(wǎng)、子圖鄰接(Adjacent)度、入度和出度路徑、路徑長度、

5、回路/環(huán)、簡單路徑連通圖、連通分量、生成樹強連通圖、強連通分量v1v2v3v4G1v1v2v3v5v4v4G2 摸底：課堂提問87.2 圖的存儲結(jié)構(gòu)圖的特點：非線性結(jié)構(gòu)（m :n ）鄰接表鄰接多重表十字鏈表設(shè)計為鄰接矩陣鏈?zhǔn)酱鎯Y(jié)構(gòu)：順序存儲結(jié)構(gòu)：無！（多個頂點，無序可言）但可用數(shù)組描述元素間關(guān)系?？捎枚嘀劓湵碇攸c介紹：鄰接矩陣(數(shù)組)表示法鄰接表(鏈?zhǔn)?表示法9一、鄰接矩陣（數(shù)組）表示法建立一個頂點表（記錄各個頂點信息）和一個鄰接矩陣（表示各個頂點之間關(guān)系）。設(shè)圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 A.Edgenn，定義為：v1v2v3v5v4v4A例1：鄰

6、接矩陣：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析1：無向圖的鄰接矩陣是對稱的；分析2：頂點i 的度第 i 行 (列) 中1 的個數(shù)；特別：完全圖的鄰接矩陣中，對角元素為0，其余全1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點表：10例2 ：有向圖的鄰接矩陣分析1：有向圖的鄰接矩陣可能是不對稱的。分析2：頂點的出度=第i行元素之和，

7、OD( Vi )= A.Edge i j 頂點的入度=第i列元素之和。ID( Vi )= A.Edge j i 頂點的度=第i行元素之和+第i列元素之和, 即：TD(Vi)=OD( Vi ) + ID( Vi )v1v2v3v4A鄰接矩陣：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：在有向圖的鄰接矩陣中， 第i行含義：結(jié)點vi的出度邊(即以vi為頭的?。?； 第i列含義：結(jié)點vi的入度邊 (即以vi為尾的?。?。頂點表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0

8、0 0 1 1 0 0 0 11 容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（弧）、找頂點的鄰接點等等。 n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。特別討論 ：網(wǎng)（即有權(quán)圖）的鄰接矩陣定義為：A.Edge i j =Wij 或（vi, vj）VR 無邊（?。﹙1v2v3v4Nv5v65489755613以有向網(wǎng)為例：鄰接矩陣： N.Edge =( v1 v2 v3 v4 v5 v6 )鄰接矩陣法優(yōu)點：鄰接矩陣法缺點：頂點表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 12注：用兩個數(shù)組分別存儲頂點

9、表和鄰接矩陣#define INFINITY INT_MAX /最大值#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點數(shù)typedef enum DG, DN, AG,AN GraphKind; /有向/無向圖，有向/無向網(wǎng)typedef struct ArcCell /?。ㄟ叄┙Y(jié)點的定義 VRType adj; /頂點間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型 InfoType *info; /該弧相關(guān)信息的指針ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;typedef struct /圖的定義 VertexType

10、vexs MAX_VERTEX_NUM ; /頂點表，用一維向量即可 AdjMatrix arcs; /鄰接矩陣 Int Vernum, arcnum; /頂點總數(shù)，?。ㄟ叄┛倲?shù) GraphKind kind; /圖的種類標(biāo)志Mgraph; 圖的鄰接矩陣存儲表示（參見教材P161）對于n個頂點的圖或網(wǎng)，空間效率=O(n2)13Status CreateUDN(Mgraph &G) /無向網(wǎng)的構(gòu)造，用鄰接矩陣表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /輸入總頂點數(shù)，總弧數(shù)和信息for(i=0;iG.vexnum,;+i) scanf(&G.vexsi );

11、/輸入頂點值，存入一維向量中for(i=0; iG.vexnum; +i) /對鄰接矩陣n*n個單元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j) G.arcsij.adj=INFINITY; G.=NULL ; for(k=0;kG.arcnum;+k) /給鄰接矩陣有關(guān)單元賦初值(循環(huán)次數(shù)弧數(shù) scanf(&v1, &v2, &w); /輸入弧的兩頂點以及對應(yīng)權(quán)值 i=LocateVex(G,v1); j=LocateVex(G,v2); /找到兩頂點在矩陣中的位置(n次? G.arcsij.adj=w; /輸入對應(yīng)權(quán)值 If(Inc

12、Info) Input(*G.); /如果弧有信息則填入 G.arcsij = G.arcs j i； /無向網(wǎng)是對稱矩陣 return OK; / CreateUDN 例：用鄰接矩陣生成無向網(wǎng)的算法（參見教材P162）對于n個頂點e條弧的網(wǎng)，建網(wǎng)時間效率 = O(n2+n+e*n)14二、鄰接表（鏈?zhǔn)剑┍硎痉ǎ亨徑颖?頭結(jié)點表+單鏈表所有頂點構(gòu)成一張用順序存儲結(jié)構(gòu)（如數(shù)組）存儲的頭結(jié)點表。一個頭結(jié)點（設(shè)為2個域），存頂點vi信息，并指向一個與vi相關(guān)的單鏈表；adjvexnextarcinfodatafirstarc單鏈表結(jié)點ArcNode頭結(jié)點VNode鄰接點域，表示

13、vi在頂點表中位置序號鏈域，指向vi下一個邊或弧的結(jié)點數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域，存儲頂點vi 信息鏈域，指向單鏈表的第一個結(jié)點對每個頂點vi 建立一個單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或出度邊）鏈接起來，表中每個結(jié)點都設(shè)為3個域；15例1：無向圖的鄰接表v1v2v3v5v4v4鄰接表0123413341420例2：有向圖的鄰接表v1v2v3v4V4V3V2V12301鄰接表(出邊)V4V3V2V13020逆鄰接表(入邊)注：鄰接表不唯一，因各個邊結(jié)點的鏈入順序是任意的。v1v2v3v4v52314200123012316圖的鄰接表存儲表示（參見教材P163）#define MA

14、X_VERTEX_NUM 20 /假設(shè)的最大頂點數(shù)typedef struct ArcNode int adjvex; /該弧所指向的頂點位置 struct ArcNode *nextarcs; /指向下一條弧的指針 InfoArc *info; /該弧相關(guān)信息的指針 ArcNode；typedef struct VNode /頂點結(jié)構(gòu) VertexType data; /頂點信息 ArcNode * firstarc; /指向依附該頂點的第一條弧的指針VNode, AdjList MAX_VERTEX_NUM ; typedef struct /圖結(jié)構(gòu) AdjList vertics ; /

15、應(yīng)包含鄰接表 int vexnum, arcnum; /應(yīng)包含頂點總數(shù)和弧總數(shù) int kind; /還應(yīng)說明圖的種類（用標(biāo)志）ALGraph; /圖結(jié)構(gòu)圖的鄰接表生成算法作為自測題。空間效率為O(n+2e)或O(n+e)時間效率為O(n+e*n)17例3：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。8064125當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！18分析1: 對于n個頂點e條邊的無向圖，鄰接表中除了n個頭結(jié)點外，只有2e個表結(jié)點,空間效率為O(n+2e)。若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。鄰接表存儲法的特點：分析2:在有向圖中，鄰接表中除了n個頭結(jié)點外，只有e個表結(jié)

16、點,空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。它其實是對鄰接矩陣法的一種改進(jìn)怎樣計算無向圖頂點的度？鄰接表的缺點：怎樣計算有向圖頂點的出度？怎樣計算有向圖頂點的入度？怎樣計算有向圖頂點Vi的度：需遍歷全表鄰接表的優(yōu)點：TD(Vi)=單鏈表中鏈接的結(jié)點個數(shù)OD(Vi)單鏈出邊表中鏈接的結(jié)點數(shù)I D( Vi ) 鄰接點為Vi的弧個數(shù)TD(Vi) = OD( Vi ) + I D( Vi )空間效率高；容易尋找頂點的鄰接點；判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。19討論：鄰接表與鄰接矩陣有什么異同之處？1. 聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一

17、行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2. 區(qū)別： 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3. 用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（en2)20自學(xué)三、十字鏈表/Orthogonal List（適用于有向圖）四、鄰接多重表/Adjacency Multilist（適用于無向圖）21 它是有向圖的另一種鏈?zhǔn)浇Y(jié)構(gòu)。 思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結(jié)合。1、每條弧對應(yīng)一個結(jié)點(稱為弧結(jié)點

18、，設(shè)5個域）2、每個頂點也對應(yīng)一個結(jié)點（稱為頂點結(jié)點，設(shè)3個域）tailvexheadvexHlinktlinkinfo頂點結(jié)點弧結(jié)點三、十字鏈表（自學(xué)）tailvex: 弧尾頂點位置 headvex: 弧頭頂點位置hlink: 弧頭相同的下一弧位置tlink: 弧尾相同的下一弧位置info: 弧信息 n個頂點用順序存儲結(jié)構(gòu) data : 存儲頂點信息。Firstin : 以頂點為弧頭的第一條弧結(jié)點。Firstout: 以頂點為弧尾的第一條弧結(jié)點。dataFirstinFirstout適用于有向圖22#define MAX_VERTEX_NUM 20typedef struct ArcBox /弧結(jié)點結(jié)構(gòu) int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox；typedef struct VexNode /頂點結(jié)構(gòu) VertexType data; ArcBox * firstin,*firstout;VexNode; typedef struct VexN