【正文】 空間復(fù)雜度和建表的時間復(fù)雜度都與鄰接表相同。 27 討論：鄰接表與鄰接矩陣有什么異同之處？ 1. 聯(lián)系： 鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。 // 該弧相關(guān) 信息的指針 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 非線性結(jié)構(gòu) （ m :n） 鄰接矩陣 ?鄰接表 ?十字鏈表 ?鄰接多重表 各種表示法成立的原則：存入電腦后能唯一復(fù)原 16 ① 建立一個 頂點表 和一個 鄰接矩陣 。 插入或刪除頂點 InsertVex(amp。 10 連通圖： 無向 圖 G中任意兩個頂點之間都有路徑相連通。 4 E A C B D 例如 : G = (V, VR) 其中 V={A, B, C, D, E} VR={A,B, A,E, B,C, C,D, D,B, D,A, E,C } 無向圖： 由頂點集和邊集構(gòu)成的圖 (“邊 ” 無方向） 若 v, w?VR 必有 w, v?VR, 則稱 (v,w) 為頂點 v 和頂點 w 之間存在一條邊。 鄰接點： 若邊 (v,w) ∈ VR，則 頂點v 和頂點 w 互為鄰接點。 PutVex(amp。G, v, w)?？臻g效率為 O(n2)。 v1 v2 v3 v4 v5 2 3 ^ 1 4 2 ^ 0 v1鄰接點 v4的位置 此無權(quán)圖未開第 3分量 TD(Vi)=單鏈表中 Vi鏈接的結(jié)點個數(shù) 24 例 2：有向圖的鄰接表如何表示？ v1 v2 v3 v4 V4 V3 ^ V2 V1 2 ^ 3 ^ 0 ^ 1 鄰接表 (出邊 ) V4 V3 V2 V1 ^ 3 ^ 0 ^ 2 ^ 0 逆鄰接表 (入邊 ) 0123 0123 在有向圖的鄰接表中不易找到指向該頂點的弧。 //還應(yīng)說明圖的種類（用標志） }ALGraph。 mark ivex ilink jvex jlink 邊結(jié)點 data firstedge 頂點結(jié)點 1 2 1 ^ 4 2 3 2 ^ 4 3 ^ 4 ^ 0 v1 1 v2 2 v3 3 v4 4 v5 0 1 2 3 4 0 1 ^… 0 3 (v1,v2) (v1,v4) (v2,v5) (v2,v3) (v3,v4) (v3,v5) (v4,v5) 。 //應(yīng)包含鄰接表 int vexnum, arum。 ② 每個單鏈表還應(yīng)當附設(shè)一個 表頭結(jié)點 （設(shè)為 2個域），存 vi信息； adjvex nextarc info data firstarc 表結(jié)點 頭結(jié)點 鄰接點域，表示 vi 鄰接點的位置 鏈域， 指向下一條邊或弧的結(jié)點 數(shù)據(jù)域，存儲頂點vi 信息 鏈域， 指向單鏈表的第一個結(jié)點 ③ 每個單鏈表的 頭結(jié)點另外用順序存儲結(jié)構(gòu) 存儲。 頂點表： 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 19 例 3 ： 有權(quán)圖（即網(wǎng)絡(luò)）的鄰接矩陣如何表示？ 定義： [ i ][ j ]= Wij vi, vj 或（ vi, vj） ∈ VR ∞ 反之 v1 v2 v3 v4 N v5 v6 5 4 8 9 7 5 5 6 1 3 鄰接矩陣： = (v1 v2 v3 v4 v5 v6) 頂點表： ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9