數據結構7圖A課件

1、數據結構課程的內容多對多（m:n)17.1 基本術語7.2 存儲結構7.3 圖的遍歷7.4 圖的其他運算7.5 圖的應用第7章 圖27.1 圖的基本術語圖：記為 G( V, E )，其中： V 是G的頂點集合，是有窮非空集； E 是G的邊集合，是有窮集。問：當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設有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。子 圖：帶權圖：即邊上帶權的圖。其中權是指每條邊可以標上具有某種含義的數值（即與邊相關的數）。帶權圖網 絡：5鄰接點：有向邊 是G中的一條邊，則稱 u 鄰接到 v。 頂點v的度是與它相關聯的邊的條數。記作TD(v)。 在有向

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

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

5、回路/環(huán)、簡單路徑連通圖、連通分量、生成樹強連通圖、強連通分量v1v2v3v4G1v1v2v3v5v4v4G2 摸底：課堂提問87.2 圖的存儲結構圖的特點：非線性結構（m :n ）鄰接表鄰接多重表十字鏈表設計為鄰接矩陣鏈式存儲結構：順序存儲結構：無！（多個頂點，無序可言）但可用數組描述元素間關系?？捎枚嘀劓湵碇攸c介紹：鄰接矩陣(數組)表示法鄰接表(鏈式)表示法9一、鄰接矩陣（數組）表示法建立一個頂點表（記錄各個頂點信息）和一個鄰接矩陣（表示各個頂點之間關系）。設圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是一個二維數組 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 的個數；特別：完全圖的鄰接矩陣中，對角元素為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行含義：結點vi的出度邊(即以vi為頭的?。?； 第i列含義：結點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 容易實現圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。 n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。特別討論 ：網（即有權圖）的鄰接矩陣定義為：A.Edge i j =Wij 或（vi, vj）VR 無邊（?。﹙1v2v3v4Nv5v65489755613以有向網為例：鄰接矩陣： 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注：用兩個數組分別存儲頂點

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

10、vexs MAX_VERTEX_NUM ; /頂點表，用一維向量即可 AdjMatrix arcs; /鄰接矩陣 Int Vernum, arcnum; /頂點總數，?。ㄟ叄┛倲?GraphKind kind; /圖的種類標志Mgraph; 圖的鄰接矩陣存儲表示（參見教材P161）對于n個頂點的圖或網，空間效率=O(n2)13Status CreateUDN(Mgraph &G) /無向網的構造，用鄰接矩陣表示scanf(&G.vexnum, &G.arcnum, &IncInfo); /輸入總頂點數，總弧數和信息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) /給鄰接矩陣有關單元賦初值(循環(huán)次數弧數 scanf(&v1, &v2, &w); /輸入弧的兩頂點以及對應權值 i=LocateVex(G,v1); j=LocateVex(G,v2); /找到兩頂點在矩陣中的位置(n次? G.arcsij.adj=w; /輸入對應權值 If(Inc

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

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

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

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

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

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

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