【正文】 儲(chǔ)結(jié)構(gòu) ? 1) 為每個(gè)頂點(diǎn)建立一個(gè)單鏈表 ， ? 2) 第 i個(gè)單鏈表中包含頂點(diǎn) Vi的所有鄰接頂點(diǎn) 。 ? 前綴編碼：一種非等長編碼。 28/32 二 . 構(gòu)造 Huffman樹 ? 算法 : – 1）將 n個(gè)帶權(quán)值 wi（ i≤n）的結(jié)點(diǎn)構(gòu)成 n棵二叉樹的集合 T={T1， T2， …… ， Tn}，每棵二叉樹只有一個(gè)根結(jié)點(diǎn)。 例 ， G1中 V2的度是 3。 ? 有向圖 1)入度 :以某頂點(diǎn)為弧頭的弧的數(shù)目 。 – 有向圖中 ， 若弧 (Ｖ x,Ｖ y)?E， 則Ｖ y是Ｖ x的鄰接點(diǎn) 。 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ù)組稱為 鄰接矩陣 。 – 3) 重復(fù) 2)，直到全部頂點(diǎn)都被訪問。 ? Huffman編碼：一種前綴編碼。 重復(fù)上述過程 ， 直到不存在未訪問過的鄰接點(diǎn)為止 。 例如 :G1中 V1到 V3的路徑為 :(V1V2V3)或 (V1V3) G2中 ， 1到 4的路徑為 134。 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)系 。 o o o o v1 v2 v3 v4 G1 1 3 4 2 G2 8/32 、長度 ? 路徑 圖中從頂點(diǎn) Vx到頂點(diǎn) Vy的頂點(diǎn)序列稱為從 Vx到 Vy的路徑 ,路徑可能是不唯一的 。 o o o o v1 v2 v3 v4 G1 NULL V3 V2 NULL V2 NULL V2 V1 V1 V4 NULL V3 19/32 G2的鄰接表 1 2 3 4 NULL 2 3 1 NULL 1 3 2 4 G2 NULL 4 NULL 20/32 圖的遍歷 ? 圖的遍歷 從指定頂點(diǎn)出發(fā)訪問圖中每一個(gè)頂點(diǎn) ， 使每個(gè)頂點(diǎn)都被訪問且只被訪問一次 ? 常用的遍歷方法： – 深度優(yōu)先遍歷法 – 廣度優(yōu)先遍歷法 21/32 一 . 深度優(yōu)先遍歷法 ? 算法： – 1) 訪問圖中某個(gè)指定頂點(diǎn) V0； – 2) 從 V0出發(fā) ， 訪問與 V0鄰接的頂點(diǎn) V1后 ，再從 V1出發(fā) ， 訪問與 V1鄰接且未被訪問過的頂點(diǎn) V2。 a 0 b 0 1 c d 0 1 1 編碼： A（ 0） B（ 10） C（ 110） D（ 111） 方法約定： 1）左分支為‘ 0’