圖的定義和術語及存儲結構-文庫吧資料
2025-07-31 03:44本頁面
【正文】 接的結點個數(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 在有向圖的鄰接表中不易找到指向該頂點的弧。 ② 每個單鏈表還應當附設一個 表頭結點 （設為 2個域），存 vi信息； adjvex nextarc info data firstarc 表結點 頭結點 鄰接點域，表示 vi 鄰接點的位置 鏈域， 指向下一條邊或弧的結點 數(shù)據(jù)域，存儲頂點vi 信息 鏈域， 指向單鏈表的第一個結點 ③ 每個單鏈表的 頭結點另外用順序存儲結構 存儲。 // 圖的種類標志 } MGraph。 // 鄰接矩陣 int vexnum, arum。 typedef struct { // 圖的定義 VertexType vexs[MAX_VERTEX_NUM]。 InfoType *info。 // VRType是頂點關系類型。 圖的鄰接矩陣在機內(nèi)如何表示？ （參見教材 P161） 注： 用兩個數(shù)組分別存儲頂點表和鄰接矩陣 define INFINITY INT_MAX //最大值 ∞ define MAX_VERTEX_NUM 20 //假設的最大頂點數(shù) typedef enum {DG, DN, UDG,UDN } GraphKind?？臻g效率為 O(n2)。 頂點表： 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 19 例 3 ： 有權圖（即網(wǎng)絡）的鄰接矩陣如何表示？ 定義： [ 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 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ v1 v2 v3 v4 v5 v6 20 容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（弧）、找頂點的鄰接點等等。 頂點的度 =第 i行元素之和 +第 i列元素之和。 分析 2： 頂點 vi的出度 =第 i行元素之和 。 1. 鄰接矩陣（數(shù)組）表示法 ??? ??? , ),( , ,]][[.否則或者如果01AEjiEjijia r c s記錄各個頂點信息 表示各個頂點之間關系 ② 設圖 A = (V, E ) 有 n 個頂點，則圖的鄰接矩陣是一個二維數(shù)組 [n][n]，定義為： 17 分析 1： 無向圖的鄰接矩陣是對稱的； 分析 2： 頂點 i 的度 ＝第 i 行 (列 ) 中 1 的個數(shù) ； 特別：完全圖的鄰接矩陣中，對角元素為 0，其余全 1。 遍 歷 15 圖的存儲結構 圖的特點： 鏈式存儲結構： 順序存儲結構： 難！ （多個頂點，無序可言，無法僅以頂點坐標表達相互關系） 可用 多
環(huán)評公示相關推薦
鄂ICP備17016276號-1