非線性數(shù)據(jù)結(jié)構(gòu)--圖-wenkub
2022-08-29 14:45:48 本頁面
【正文】 2 一 .鄰接矩陣 ? 圖為 V和 E的集合 ,因此 : – 用一個一維數(shù)組存放所有頂點； – 用一個二維數(shù)組存放頂點間關(guān)系（邊或弧）的數(shù)據(jù)，這個二維數(shù)組稱為 鄰接矩陣 。 – 有向圖 – 第 i行的元素之和為頂點 Vi的出度；第 j列的元素之和為頂點 Vj的入度 。 17/32 二 . 鄰接表 ? 結(jié)點組成 ： ? 每個鏈表附設一個頭結(jié)點 ， 結(jié)構(gòu)為： adjvex data nextarc 頂點 Vi的鄰接點 與邊或弧有關(guān)的權(quán)值 指向 Vi的下一個 鄰接點的指針 Vexdata firstarc 指向 Vi單鏈表的第一個結(jié)點 存放 Vi信息 18/32 1. 無向圖的鄰接表 V1 V2 V3 V4 V2 頂點 Vi的度恰好就是 第 i個單鏈表中的結(jié)點數(shù)。 22/32 V1 V3 V2 V5 V4 V6 G6 深度優(yōu)先遍歷法舉例 遍歷過程 訪問頂點 所過邊 ?起點 V1 V1 ?V1的第 1個鄰接點 V3 V3 （ V1， V3） ?V3的第 1個鄰接點 V1已訪問，取下 一個鄰接點 V5 V5 （ V3， V5） ?V5的第 1個鄰接點 V3已訪問，取下 一個鄰接點 V2 V2 （ V5， V2） ?V2的兩個鄰接點均被訪問， 回退到 V5， V5的鄰接點均被訪問， 回退到 V3， V3的鄰接點均被訪問 ， 回退到 V1， V1的另一個鄰接點 V4 未被訪問 V4 （ V1， V4） ?V4的第一個鄰接點 V1已被訪問， 另一個鄰接點 V6未被訪問 V6 （ V4， V6） ?V6的鄰接點被訪問，回退到 V4 ?V4的鄰接點均被訪問 ?回退到 V1，返回到出發(fā)點，遍歷結(jié)束。 – 3) 重復 2)，直到全部頂點都被訪問。 – 2）在 T中選取兩個權(quán)值最小的結(jié)點作為左右子樹，構(gòu)成一個新的二叉樹，其根結(jié)點的權(quán)值取左右子樹權(quán)值之和； – 3）在 T中刪除這兩棵樹，將新構(gòu)成的樹加入到 T中； – 4）重復 2）、 3）步，直到 T中只含一棵樹為止，該樹就是 Huffman樹。任一個字符的編碼都不是另一個字符編碼的前綴。 W={3 1 2 1} 3 1 2 1 W={3 2 2} 1 1 2 W= {3 2 2} 1 1 2 2 4 W={3 4} 1 1 2 2 4 1 1 2 2
數(shù)學相關(guān)推薦
鄂ICP備17016276號-1