圖的定義和術語及存儲結構.ppt

1、1,數(shù)據(jù)結構課程的內容：,多對多 （m:n),2,7.1 基本術語 7.2 存儲結構 7.3 圖的遍歷 7.4 圖的連通性 7.5 圖的應用,第7章 圖,3,7.1 圖的基本術語,其中：V 是G 的頂點集合，是有窮非空集； VR| v,wV 且 P(v,w),是有窮集.,問：當VR 為空時，圖G存在否？,V=vertex,圖：記為 Graph( V, VR ),表示從 v 到 w 的一條弧，并稱 w 為弧頭，v 為弧尾。 P(v,w) 定義了弧 的意義或信息。,答：還存在！但此時圖G只有頂點。,4,例如:,G = (V, VR),其中 V=A, B, C, D, E VR=, , , , ,

2、, ,無向圖：由頂點集和邊集構成的圖(“邊”無方向）,若VR 必有VR, 則稱 (v,w) 為頂點 v 和頂點 w 之間存在一條邊。,有向圖：由頂點集和弧集構成的圖（“弧”是有方向的）,5,例如: G=(V,VR) 其中： V=A, B, C, D, E, F VR=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) ,若 n 個頂點的無向圖有 n(n-1)/2 條邊, 稱為無向完全圖 若 n 個頂點的有向圖有n(n-1) 條邊, 稱為有向完全圖,證明：,有向完全圖有n(n-1)條邊。,證明：若是有向完全圖，則n個頂點中的每個頂點都有一

3、條弧指向其它n-1個頂點, 因此總邊數(shù)=n(n-1),6,證明：從可以直接推論出無向完全圖的邊數(shù)因為無方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。,無向完全圖有n(n-1)/2 條邊。,例：判斷下列4種圖形各屬什么類型？,7,稀疏圖：稠密圖：,設有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱 圖G 是 圖G 的子圖。,子 圖：,邊較少的圖。通常邊數(shù)遠少于nlogn 邊很多的圖。,無向圖中，邊數(shù)接近n(n-1)/2 有向圖中，邊數(shù)接近n(n-1),B,例如：,8,15,9,7,21,11,3,2,有向網(wǎng)或無向網(wǎng)是弧或邊帶權的圖。,鄰接點：若邊(v,

4、w) VR，則頂點v 和頂點w 互為鄰接點。,邊(v,w) 依附于頂點v 和w，或者與頂點v,w相關聯(lián) 。,頂點v的度：是和v 相關聯(lián)的邊的數(shù)目,記為TD(v).,頂點v的出度: 以頂點v 為尾的弧的數(shù)目;記為OD(v).,頂點v的入度: 以頂點v 為頭的弧的數(shù)目,記為ID(v).,頂點的度(TD)=出度(OD)+入度(ID),問：當有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？,答：是樹！而且是一棵有向樹！,9,路徑:設圖G=(V,VR)中的一個頂點序列: v=vi,0 ,vi,1 , , vi,m=w 中，(vi,j-1 ,vi,j)（或 vi,j-1,vi,j） VR

5、 1jm,則稱從頂點v 到頂點w 之間存在一條路徑。 路徑長度：路徑上邊（或?。┑臄?shù)目。,如:從A到F長度為 3 的路徑A,B,C,F或A，E，C，F(xiàn),簡單路徑:指序列中頂點不重復出現(xiàn)的路徑。,簡單回路:指序列中第一個頂點和最后一個頂點相同，其余頂點不重復出現(xiàn)的回路。,10,連通圖：無向圖G中任意兩個頂點之間都有路徑相連通。,連通分量：非連通圖中的極大連通子圖。,強連通圖：在有向圖中, 每一對頂點vi和vj, 都存在一條從vi到vj和從vj到vi的路徑,強連通分量：非強連通圖中的極大強連通子圖。,11,生成樹：,生成森林：,假設一個連通圖有 n 個頂點和 e 條邊，其中 n-1 條邊和 n 個

6、頂點構成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。,由若干棵生成樹組成，含全部頂點，但構成這些樹的邊是最少的。（對有向或無向圖均適用）,12,CreatGraph( /返回v的“第一個鄰接點” 若該頂點在G中沒有鄰接點，則返回“空”。,NextAdjVex(G, v, w); /返回v的（相對于w的） “下一個鄰接點”。若w是v的最后一個鄰接點，則返回“空”。,插入或刪除頂點,InsertVex( /在圖G中增添新頂點v。,DeleteVex( /從頂點v起深度優(yōu)先遍歷圖G，并對每個頂點調用函數(shù)Visit一次且僅一次。,BFSTraverse(G, v, Visit(); /從頂點

7、v起廣度優(yōu)先遍歷圖G，并對每個頂點調用函數(shù)Visit一次且僅一次。,遍 歷,15,7.2 圖的存儲結構,圖的特點：,鏈式存儲結構：,順序存儲結構：,難！,（多個頂點，無序可言，無法僅以頂點坐標表達相互關系）,可用多重鏈表,鄰接矩陣(數(shù)組)表示法 鄰接表(鏈式)表示法 十字鏈表表示法 鄰接多重表表示法,但可用數(shù)組描述元素間關系。,非線性結構（m :n）,鄰接矩陣,鄰接表 十字鏈表 鄰接多重表,各種表示法成立的原則：存入電腦后能唯一復原,16, 建立一個頂點表和一個鄰接矩陣。,1. 鄰接矩陣（數(shù)組）表示法,記錄各個頂點信息,表示各個頂點之間關系, 設圖 A = (V, E ) 有 n 個頂點，則圖

8、的鄰接矩陣是一個二維數(shù)組 A.arcsnn，定義為：,17,分析1：無向圖的鄰接矩陣是對稱的； 分析2：頂點i 的度第 i 行 (列) 中1 的個數(shù)； 特別：完全圖的鄰接矩陣中，對角元素為0，其余全1。,例1：,鄰接矩陣：,A.arcs =,（ v1 v2 v3 v4 v5 ）,v1 v2 v3 v4 v5,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,頂點表：,無向圖的鄰接矩陣如何表示？,18,例2 ：有向圖的鄰接矩陣如何表示？,分析1：有向圖的鄰接矩陣可能是不對稱的。 分析2：頂點vi的出度=第i行元素之和; 頂點vi的入度=第i列元素

9、之和; 頂點的度=第i行元素之和+第i列元素之和。,鄰接矩陣：,A.arcs =,( v1 v2 v3 v4 ),v1 v2 v3 v4,注：在有向圖的鄰接矩陣中， 第i行含義：以結點vi為尾的弧(即出度邊）； 第j列含義：以結點vj為頭的弧(即入度邊）。,頂點表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,19,例3 ： 有權圖（即網(wǎng)絡）的鄰接矩陣如何表示？,定義：,鄰接矩陣：,N.arcs =,(v1 v2 v3 v4 v5 v6),頂點表：, 5 7 4 8 9 5 6 5 3 1 ,v1 v2 v3 v4 v5 v6,20,容易實現(xiàn)圖的操作，如：求某頂點的度、判斷

10、頂點之間是否有邊（?。?、找頂點的鄰接點等等。 n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。,鄰接矩陣法優(yōu)點：,鄰接矩陣法缺點：,對稀疏圖而言尤其浪費空間。,圖的鄰接矩陣在機內如何表示？ （參見教材P161）,注：用兩個數(shù)組分別存儲頂點表和鄰接矩陣 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假設的最大頂點數(shù) typedef enum DG, DN, UDG,UDN GraphKind; /有向圖，有向網(wǎng)，無向圖，無向網(wǎng),21,typedef struct ArcCell / 弧的定義 VRType adj;

11、/ VRType是頂點關系類型。 /對無權圖,用1或0表示相鄰否；對帶權圖，則為權值類型。 InfoType *info; / 該弧相關信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef struct / 圖的定義 VertexType vexsMAX_VERTEX_NUM; / 頂點向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 頂點數(shù)，弧數(shù) GraphKind kind; / 圖的種類標志 MGraph;,22,2. 鄰接表（鏈式）表示法, 對每個頂點vi 建立一個單鏈表

12、，把與vi有關聯(lián)的邊（或以vi為尾的弧)的信息鏈接起來，表中每個結點都設為3個域。, 每個單鏈表還應當附設一個表頭結點（設為2個域），存vi信息；,表結點,頭結點,鄰接點域，表示vi 鄰接點的位置,鏈域，指向下一條邊或弧的結點,數(shù)據(jù)域，存儲頂點vi 信息,鏈域，指向單鏈表的第一個結點, 每個單鏈表的頭結點另外用順序存儲結構存儲。,邊或弧的信息,23,例1：無向圖的鄰接表如何表示？,鄰接表：,請注意：鄰接表不唯一！因各個邊結點的鏈入順序是任意的。,v1鄰接點v4的位置,此無權圖未開第3分量,TD(Vi)=單鏈表中Vi鏈接的結點個數(shù),24,例2：有向圖的鄰接表如何表示？,鄰接表(出邊),逆鄰接表(

13、入邊),0123,0123,在有向圖的鄰接表中不易找到指向該頂點的弧。,OD(Vi)=鄰接表中Vi鏈接的結點數(shù)ID(Vi)=逆鄰接表中Vi鏈接的結點數(shù),TD(Vi) = OD( Vi ) + ID( Vi ),25,例3：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡。,80,64,1,2,5,當鄰接表的存儲結構形成后，圖便唯一確定！,26,分析1：對于n個頂點e條邊的無向圖，鄰接表中除了n個頭結點外，只有2e個表結點,空間效率為O(n+2e)。 若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。,鄰接表存儲法的特點：,分析2:在有向圖中，鄰接表中除了n個頭結點外，只有e個表結點,空間效率為O

14、(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。,它其實是對鄰接矩陣法的一種改進，兩個結點表示一條邊或弧,鄰接表的缺點：,鄰接表的優(yōu)點：,空間效率高；容易尋找頂點的鄰接點；,判斷兩頂點間是否有邊或弧，需搜索兩結點對應的單鏈表，沒有鄰接矩陣方便。,27,討論：鄰接表與鄰接矩陣有什么異同之處？,1. 聯(lián)系：鄰接表中每個鏈表對應于鄰接矩陣中的一行，鏈表中結點個數(shù)等于一行中非零元素的個數(shù)。 2. 區(qū)別： 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關）。 鄰接矩陣的空間復雜度為O(n2),而鄰接表的空間復雜度為O(n+e)。 3. 用途： 鄰接矩

15、陣多用于稠密圖的存儲（e接近n(n-1)/2)； 而鄰接表多用于稀疏圖的存儲（en2),28,圖的鄰接表在機內如何表示？ （參見教材P163）,#define MAX_VERTEX_NUM 20 /假設的最大頂點數(shù),Typedef struct ArcNode /弧結構 int adjvex; /該弧所指向的頂點位置 struct ArcNode *nextarcs; /指向下一條弧的指針 InfoArc *info; /該弧相關信息的指針 ArcNode；,29,Typedef struct /圖結構 AdjList vertics ; /應包含鄰接表 int vexnum, arcnum;

16、 /應包含頂點總數(shù)和弧總數(shù) int kind; /還應說明圖的種類（用標志） ALGraph;,Typedef struct VNode /頂點結構 VertexType data; /頂點信息 ArcNode * firstarc; /指向第一條依附該頂點的弧的指針 VNode, AdjList MAX_VERTEX_NUM ; /鄰接表,30,它是有向圖的另一種鏈式存儲結構。 思路：將鄰接矩陣用鏈表存儲，是鄰接表、逆鄰接表的結合。 (1)開設弧結點，設5個域（每段弧是一個數(shù)據(jù)元素） (2)開設頂點結點，設3個域（每個頂點也是一個數(shù)據(jù)元素）,弧結點,3. 十字鏈表表示法,tailvex: 弧

17、尾頂點位置 headvex: 弧頭頂點位置 hlink: 弧頭相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息,31,data : 頂點信息 firstin : 以頂點為弧頭的第一條弧結點 firstout: 以頂點為弧尾的第一條弧結點,問：n個頂點的集合怎樣儲存？,順序存儲結構,頂點結點,十字鏈表優(yōu)點：容易操作，如求頂點的入度、出度等。,空間復雜度和建表的時間復雜度都與鄰接表相同。,32,0 1 2,例：畫出有向圖的十字鏈表。,弧結點,頂點結點,33,這是無向圖的另一種鏈式存儲結構，當對邊操作時建議采用此種結構存儲。 （1）設立邊結點， 6個域（每條邊是一個數(shù)據(jù)元素） （2）設立頂點結點， 2個域（每個頂點也是一個數(shù)據(jù)元素）,邊結點,4. 鄰接多重表表示法,mark：標志域，標記該邊是否被搜索過。 ivex， jvex :