重要的贪心算法

最优前缀码

二元前缀码

• 二元前缀码
用0-1字符串作为代码表示字符，要求任何字符的代码都不能作为其它字符代码的前缀
• 非前缀码的例子
a: 001, b: 00, c: 010, d: 01
• 解码的歧义，例如字符串 0100001
解码1: 01, 00, 001 d, b, a
解码2: 010, 00, 01 c, b, d

小结

• 二元前缀码及其二叉树表示
• 给定频率下的平均传输位数计算公式
• 最优前缀码——平均传输位数最少
• 哈夫曼算法
• 前缀码的性质

哈夫曼算法的证明及应用

算法正确性证明思路

定理 Huffman 算法对任意规模为n（n≥2）的字符集C 都得到关于C 的最优前缀码的二叉树.
归纳基础 证明：对于n=2的字符集,Huffman算法得到最优前缀码.
归纳步骤 证明：假设Huffman算法对于规模为 k 的字符集都得到最优前缀码，那么对于规模为k+1的字符集也得到最优前缀码.

小结

• 哈夫曼算法的正确性证明：对规模归纳
• 哈夫曼算法的应用：文件归并

最小生成树

无向连通带权图
G = (V, E, W)，
其中 w(e)∈W 是边 e 的权.

G 的一棵生成树 T 是包含了G 的所有顶点的树, 树中各边的权之和
W(T) 称为树的权，具有最小权的生成树称为 G 的最小生成树.

求最小生成树

问题：
给定连通带权图 G = (V, E, W)，w(e)∈W是边 e 的权. 求 G 的一棵最小生成树.

贪心法：
Prim 算法，
Kruskal 算法

生成树在网络中有着重要应用

小结

• 生成树与生成树的权
• 最小生成树
• 生成树的性质