非線性數(shù)據(jù)結(jié)構(gòu)--圖-wenkub.com
2025-07-29 14:45 本頁面
【正文】 以給定權(quán)值的結(jié)點構(gòu)造 Huffman樹，按二進(jìn)制前綴編碼的方式構(gòu)成的編碼 例：設(shè)要傳送的電文是： abaccda ， 有 4個字符 abcd， 可分別編碼為 00、 0 11，則電文是： 00010010101100，共 14位，可采用哈夫曼編碼縮短長度： 字母 abcd出現(xiàn)頻率分別為： 1。 ? 前綴編碼：一種非等長編碼。 28/32 二 . 構(gòu)造 Huffman樹 ? 算法 : – 1）將 n個帶權(quán)值 wi（ i≤n）的結(jié)點構(gòu)成 n棵二叉樹的集合 T={T1， T2， …… ， Tn}，每棵二叉樹只有一個根結(jié)點。然后 ,依此從W1,W2,… ,Wk出發(fā)訪問各自未被訪問的鄰接點。 – 3) 回退到尚未訪問過的頂點 ,從該頂點出發(fā) ， 重復(fù) 1)、 2)， 直到全部被訪問過的鄰接點都被訪問為止 。 V1 V2 V3 V4 G5 2 3 5 7 16/32 二 . 鄰接表 ? 圖的鏈?zhǔn)酱鎯Y(jié)構(gòu) ? 1) 為每個頂點建立一個單鏈表 ， ? 2) 第 i個單鏈表中包含頂點 Vi的所有鄰接頂點 。 例 ， G1中 V2的度是 3。 ? 網(wǎng) 帶權(quán)的圖稱為網(wǎng) 。 ? 長度 路徑上邊或弧的數(shù)目 。 3)頂點的度 =入度 +出度 。 ? 有向圖 1)入度 :以某頂點為弧頭的弧的數(shù)目 。 ? 弧頭 : 弧的終點 ? 弧尾 : 弧的起點 弧 〈 Vx， Vy〉 弧尾 Vx 弧頭 Vy 6/32 4. 鄰接點 ? 頂點 : 圖中的結(jié)點 ? 鄰接點 : – 無向圖中 ， 若邊 (Ｖ x,Ｖ y)?E， 則Ｖ x、 Ｖ y互為鄰接點 。 3/32 一 . 圖的定義 ? 1. 定義 : 圖 G =(V， E) 其中： V:頂點的非空集合 E:頂點的偶對 邊的集合 ? 例 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. 有向圖、無向圖 ? 無向圖 : 圖中頂點的偶對是無序的，稱此圖為無向圖，其偶對用 (vx， vy)表示。 ? 有向圖 : 圖中頂點的偶對是有序的，稱此圖為有向圖 ,偶對用 vx,vy表示。 – 有向圖中 ， 若弧 (Ｖ x,Ｖ y)?E， 則Ｖ y是Ｖ x的鄰接點 。 G2中頂點 1的入度為 1。 頂點 1的度 =2+1=3。 例如 ， G1中 V1到 V3的長度為 1或 2； G2中 1到 4的長度為 2。 V1 V2 V3 V4 G5 2 3 5 7 10/32 圖類的存儲結(jié)構(gòu) 常用的存儲結(jié)構(gòu)： – 鄰接矩陣表示法 – 鄰接表表示法 11/3
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1