圖的定義和術(shù)語及存儲(chǔ)結(jié)構(gòu)(編輯修改稿)
2025-08-21 03:44 本頁面
【文章內(nèi)容簡介】 ： 無向圖的鄰接矩陣是對(duì)稱的； 分析 2： 頂點(diǎn) i 的度 ＝第 i 行 (列 ) 中 1 的個(gè)數(shù) ； 特別：完全圖的鄰接矩陣中，對(duì)角元素為 0，其余全 1。 例 1： 鄰接矩陣： = （ 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 頂點(diǎn)表： 無向圖的鄰接矩陣如何表示？ v1 v2 v3 v5 v4 A 18 例 2 ：有向圖的鄰接矩陣如何表示？ 分析 1： 有向圖的鄰接矩陣可能是不對(duì)稱的。 分析 2： 頂點(diǎn) vi的出度 =第 i行元素之和 。 頂點(diǎn) vi的入度 =第 i列元素之和 。 頂點(diǎn)的度 =第 i行元素之和 +第 i列元素之和。 v1 v2 v3 v4 A 鄰接矩陣： = ( v1 v2 v3 v4 ) v1 v2 v3 v4 注： 在有向圖的鄰接矩陣中， 第 i行含義：以結(jié)點(diǎn) vi為尾的弧 (即出度邊）； 第 j列含義：以結(jié)點(diǎn) vj為頭的弧 (即入度邊）。 頂點(diǎn)表： 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) 頂點(diǎn)表： ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞ v1 v2 v3 v4 v5 v6 20 容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。 n個(gè)頂點(diǎn)需要 n*n個(gè)單元存儲(chǔ)邊 (弧 )?？臻g效率為 O(n2)。 鄰接矩陣法 優(yōu)點(diǎn)： 鄰接矩陣法 缺點(diǎn)： 對(duì)稀疏圖而言尤其浪費(fèi)空間。 圖的鄰接矩陣在機(jī)內(nèi)如何表示？ （參見教材 P161） 注： 用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣 define INFINITY INT_MAX //最大值 ∞ define MAX_VERTEX_NUM 20 //假設(shè)的最大頂點(diǎn)數(shù) typedef enum {DG, DN, UDG,UDN } GraphKind。 //{有向圖，有向網(wǎng)，無向圖，無向網(wǎng) } 21 typedef struct ArcCell { // 弧的定義 VRType adj。 // VRType是頂點(diǎn)關(guān)系類型。 //對(duì)無權(quán)圖 ,用 1或 0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型 。 InfoType *info。 // 該弧相關(guān) 信息的指針 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 typedef struct { // 圖的定義 VertexType vexs[MAX_VERTEX_NUM]。 // 頂點(diǎn)向量 AdjMatrix arcs。 // 鄰接矩陣 int vexnum, arum。 // 頂點(diǎn)數(shù)，弧數(shù)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1