圖的定義和術(shù)語及存儲(chǔ)結(jié)構(gòu)(更新版)
【正文】 ^ 2 ^ 0 逆鄰接表 (入邊 ) 0123 0123 在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。 typedef struct { // 圖的定義 VertexType vexs[MAX_VERTEX_NUM]?？臻g效率為 O(n2)。 1. 鄰接矩陣（數(shù)組）表示法 ??? ??? , ),( , ,]][[.否則或者如果01AEjiEjijia r c s記錄各個(gè)頂點(diǎn)信息 表示各個(gè)頂點(diǎn)之間關(guān)系 ② 設(shè)圖 A = (V, E ) 有 n 個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組 [n][n]，定義為： 17 分析 1： 無向圖的鄰接矩陣是對稱的； 分析 2： 頂點(diǎn) i 的度 ＝第 i 行 (列 ) 中 1 的個(gè)數(shù) ； 特別：完全圖的鄰接矩陣中，對角元素為 0，其余全 1。G, v, w)。G, v)。 PutVex(amp。 連通分量： 非連通圖中的極大連通子圖。 鄰接點(diǎn)： 若邊 (v,w) ∈ VR，則 頂點(diǎn)v 和頂點(diǎn) w 互為鄰接點(diǎn)。 有向圖： 由頂點(diǎn)集和弧集構(gòu)成的圖 （ “ 弧”是有方向的） 5 B C A F E D 例如 : 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 個(gè)頂點(diǎn)的無向圖有 n(n1)/2 條邊 , 稱為 無向完全圖 ?若 n 個(gè)頂點(diǎn)的有向圖有 n(n1) 條邊 , 稱為 有向完全圖 證明： ① 有向完全圖有 n(n1)條邊 。 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 } 無向圖： 由頂點(diǎn)集和邊集構(gòu)成的圖 (“邊 ” 無方向） 若 v, w?VR 必有 w, v?VR, 則稱 (v,w) 為頂點(diǎn) v 和頂點(diǎn) w 之間存在一條邊。 無向圖中，邊數(shù)接近 n(n1)/2 有向圖中，邊數(shù)接近 n(n1) B B C A B E C F A B E C F 例如： 8 A B E C F 15 9 7 21 11 3 2 有向網(wǎng) 或 無向網(wǎng) 是弧或邊帶權(quán)的圖 。 10 連通圖： 無向 圖 G中任意兩個(gè)頂點(diǎn)之間都有路徑相連通。 GetVex(G, v) // 返回 v 的值。 插入或刪除頂點(diǎn) InsertVex(amp。 DeleteArc(amp。 非線性結(jié)構(gòu) （ m :n） 鄰接矩陣 ?鄰接表 ?十字鏈表 ?鄰接多重表 各種表示法成立的原則：存入電腦后能唯一復(fù)原 16 ① 建立一個(gè) 頂點(diǎn)表 和一個(gè) 鄰接矩陣 。 n個(gè)頂點(diǎn)需要 n*n個(gè)單元存儲(chǔ)邊 (弧 )。 // 該弧相關(guān) 信息的指針 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 邊或弧的信息 23 例 1：無向圖的鄰接表如何表示？ v1 v2 v3 v5 v4 鄰接表： 0 1 2 3 4 ^ 1 3 3 4 ^ 1 4 2 ^ 0 請注意：鄰接表不唯一！因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。 27 討論：鄰接表與鄰接矩陣有什么異同之處？ 1. 聯(lián)系： 鄰接表中每個(gè)鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。 //應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù) int kind。 空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1