非線性數(shù)據(jù)結(jié)構(gòu)--圖-展示頁
2024-08-16 14:45本頁面
【正文】 ，則 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的度 。 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ù)組稱為 鄰接矩陣 。 權(quán)通常用來表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或費(fèi)用 。 例如 ， G1中 V1到 V3的長度為 1或 2； G2中 1到 4的長度為 2。 例如 :G1中 V1到 V3的路徑為 :(V1V2V3)或 (V1V3) G2中 ， 1到 4的路徑為 134。 頂點(diǎn) 1的度 =2+1=3。 頂點(diǎn) 1的出度為 2。 G2中頂點(diǎn) 1的入度為 1。 例如 ， G1中 V2的度為 3， V4的度為 1。 – 有向圖中 ， 若弧 (Ｖ x,Ｖ y)?E， 則Ｖ y是Ｖ x的鄰接點(diǎn) 。 ? 弧 : 有向圖中頂點(diǎn)的偶對(duì) ,〈 Vx,Vy〉 表示從Vx到 Vy。 ? 有向圖 : 圖中頂點(diǎn)的偶對(duì)是有序的，稱此圖為有向圖 ,偶對(duì)用 vx,vy表示。 1/32 非線性數(shù)據(jù)結(jié)構(gòu) 圖 ? 概念 ?有向圖、無向圖、網(wǎng) ? 存儲(chǔ) ?鄰接矩陣、鄰接表 ? 遍歷 ?深度優(yōu)先、廣度優(yōu)先 2/32 圖的邏輯結(jié)構(gòu) ? 圖是對(duì)結(jié)點(diǎn)的前趨和后繼個(gè)數(shù)不加限制的數(shù)據(jù)結(jié)構(gòu) ,用來 描述元素之間 “ 多對(duì)多 ” 的關(guān)系 。 3/32 一 . 圖的定義 ? 1. 定義 : 圖 G =(V， E) 其中： V:頂點(diǎn)的非空集合 E:頂點(diǎn)的偶對(duì) 邊的集合 ? 例 V={v1,v2,v3,v4} E={（ v1,v2),(v1,v3), （ v2,v1),(v2,v3), （ v2,v4),(v3,v1), （ v3,v2),(v4,v2) } o o o o v1 v2 v3 v4 G1 4/32 2. 有向圖、無向圖 ? 無向圖 : 圖中頂點(diǎn)的偶對(duì)是無序的，稱此圖為無向圖，其偶對(duì)用 (vx， vy)表示。 ? G2=（ V， E） V={ 1,2,3,4} E={〈 1,2,1,3
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1