非線性數(shù)據(jù)結(jié)構(gòu)--圖-文庫吧
2025-07-17 14:45 本頁面
【正文】 例如 ， G1中 V1到 V3的長度為 1或 2； G2中 1到 4的長度為 2。 1 3 2 4 G2 o o o o v1 v2 v3 v4 G1 9/32 、權(quán) ? 權(quán) 若圖的邊或弧帶有與之相關(guān)的數(shù) ， 稱此數(shù)為該邊或弧的權(quán) 。 權(quán)通常用來表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或費(fèi)用 。 ? 網(wǎng) 帶權(quán)的圖稱為網(wǎng) 。 V1 V2 V3 V4 G5 2 3 5 7 10/32 圖類的存儲(chǔ)結(jié)構(gòu) 常用的存儲(chǔ)結(jié)構(gòu)： – 鄰接矩陣表示法 – 鄰接表表示法 11/32 一 .鄰接矩陣 ? 圖為 V和 E的集合 ,因此 : – 用一個(gè)一維數(shù)組存放所有頂點(diǎn)； – 用一個(gè)二維數(shù)組存放頂點(diǎn)間關(guān)系（邊或弧）的數(shù)據(jù)，這個(gè)二維數(shù)組稱為 鄰接矩陣 。 – 鄰接矩陣又分為 有向圖鄰接矩陣 和 無向圖鄰接矩陣 。 12/32 ? 定義 設(shè)圖 G=(V,E)是有 n(n?1)個(gè)頂點(diǎn)的圖，則 G的鄰接矩陣是具有下述性質(zhì)的對(duì)稱陣： 1 (Vi， Vj） ? E A[i][j]=A[j][i] = 0 (Vi， Vj） ? E G1的鄰接矩陣為： = 1 2 3 4 A= = 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 4x4 o o o o v1 v2 v3 v4 G1 13/32 ? 定義 設(shè)圖 G=（ V， E） 是有 n（ n ? 1） 個(gè)頂點(diǎn)的圖 ，則 G的鄰接矩陣是具有下述性質(zhì)的 nxn的方陣： 1 〈 Vi， Vj? E A[i][j] = 0 〈 Vi， Vj? E 例如 ， G2的鄰接矩陣為： = 1 2 3 4 A= = 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 4x4 1 3 2 4 G2 14/32 – 無向圖 – 第 i行 （ 或第 i列 ） 的元素之和是頂點(diǎn) Vi的度 。 例 ， G1中 V2的度是 3。 – 有向圖 – 第 i行的元素之和為頂點(diǎn) Vi的出度；第 j列的元素之和為頂點(diǎn) Vj的入度 。 例 ， G2中 ，V2的出度為 0， V1的入度為 1。 G1 A= = 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 3 2 4 G2 15/32 ? 定義： Wij （ Vi,Vj） 或 〈 Vi,Vj〉 ? E A[i][j] = ? （ Vi,Vj） 或 〈 Vi,Vj〉 ? E = V1 V2 V3 V4 A==
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1