4.5 哈夫曼编码
哈夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，哈夫曼根据字符在文件中出现的不同频率来建立一个用0，1串表示各字符的最优编码树（称为哈夫曼树），它的设计也是贪心选择的一个典型例子。

例假设有一个包含10000个只含a，b，c，d，e，f字符的数据文件，各字符在文件中出现的频率见下4.5.1表
表 4.5.1
若采用等长编码，则需3位二进制数位来表示6个字符，这种方法要用30000位来表示整个文件。

若采用变长编码，则整个文件只需
(45×1+13×3+12×3+16×3+9×4+5×4) ×100=22400 位
也就是说压缩了 (30000-22400)÷30000×100%≥25% 。

实际上，这就是这个文件的最优编码方案了
4.5.1 前缀码
我们对每一字符规定一个0，1串作为其代码，并要求任一字符代码都不是其他字符代码的前缀，这样的编码简称为前缀码。

在4.5.1表中的两种编码都是前缀码。

由于任一字符代码都不是其他字符代码的前缀，所以译码方法非常简单。

为了在译码过程中方便地取出编码的前缀，我们可以用二叉树作为前缀码的数据结构。

在表示前缀码的二叉树中，树叶代表给定的字符，并将每个字符的前缀码看作是从树根到代表该字符的树叶的一条道路。

代码中每一位的0或1分别作为指示某结点到左儿子或右儿子的路标。

如图4-1中的两棵二叉树是表4.5.1中两种编码方案所对应的数据结构。

图 4-1 前缀码的二叉树表示
容易看出，表示最优编码方案所对应的前缀码的二叉树总是一棵完全二叉树，即树中任一结点都有2个儿子。

而定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。

在一般情况下，若C是编码字符集，包含有n个字符，则表示其最优前缀码的二叉树中恰好有n个叶子。

每个叶子对应于字符集中一个字符，且该二叉树恰好有n - 1个内部结点。

4.6 最小生成树
设G= （V ，E ）是一个无向连通图，即一个网络。

给 E 的每一条边（v, w ）赋于一个权。

如果G 的一个子图G ˊ是一棵包含G 的所有顶点的树，则称G ˊ为G 的生成树。

生成树上各边权的总和称为该生成树的代价。

在G 的所有生成树中，代价最小的生成树称为G 的最小生成树。

网络的最小生成树在实际中有着广泛的应用。

在不同的背景下，边的权可以代表不同的含义，比如，两点间的距离，两点间的公路造价等等。

例如，在设计通信网络时，用图的顶点表示城市，用边（v, w ）的权表示建立城市v 和城市w 的之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。

用贪心算法设计策略可以设计出构造最小生成树的有效算法。

本节中要介绍的构造最小生成树的Prim 算法和Kruskal 算法都可以看作是应用贪心算法设计策略的典型例子。

4.6.1 Prim 算法
设G= （V ，E ）是一个连通带权图，V={1 ，2 ，···，n} ，二维数组W 的元素W[i][j] 表示边（i ，j ）的权。

构造G 的一棵最小生成树的Prim 算法的基本思想是：首先置S={1} ，
然后，只要S 是V 的真子集，就作如下的贪心选择：选取满足条件i ∈S ，j ∈V -S ，且W[i][j] 最小的边，并将顶点j 添加到S 中。

这个过程一直进行到S=V 时为止。

在这个过程中选取到的所有边恰好构成G 的一棵最小生成树T 。

Prim 算法：
S1. T= Æ ，S={1} ，mincost=0
S2. 当S<>V 时转S3 ，否则转S7
S3. 设（i ，j ）是所有k ∈S ，l ∈V - S 的边（k ，l ）中权最小的边
S4. T=T ∪{ （i ，j ）}
S5. S=S ∪{ j }
S6. mincost=mincost+W[i][j] ，转S2
S7. 输出T ，mincost
其实，S 并不一定从顶点1 开始，可以从任一个顶点开始。

例对于图4 -3 a ，图4 -3 b 是Prim 算法生成最小生成树的过程。

图4 -3 a 图 4 -3 b 最小生成树的生成过程
算法实现时，时间主要消耗在双层循环上，所以总的时间复杂性为○ (n2)。

4.7 单源最短路径问题
给定一个带权有向图G=（V，E），其中每条边的权是一个非负数。

另外，还给定V中的一个顶点，称为源。

现在我们要计算从源到所有其他各个顶点的最短路长度。

这里路的长度是指路上各边权之和。

这个问题称为单源最短路径问题。

Dijkstra算法是解单源最短路径问题的一个贪心算法。

其基本思想是：设置一个顶点集合S并不断地作贪心选择来扩充这个集合。

一个顶点属于集合S
当且仅当从源到该顶点的最短路径长度已知。

初始时，S中仅含有源。

设u是G 的某一个顶点，我们把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组DIST来记录当前每个顶点所对应的最短特殊路径长度。

Dijkstra 算法每次从V-S中取出具有最短特殊路径长度的顶点u添加到S中。

当顶点u
添加到S中后，与顶点u相临的顶点v的最短特殊路径长度可能改变，如果长度改变了，则它必定是由一条从源开始，经过u然后到w的更短的路所造成的，此时，可以修改DIST[w]=DIST[u]+边(u, w)的权。

一旦S包含了V中的所有顶点，DIST就记录了从源到所有其他顶点之间的最短路径长度。

在下面的算法中，集合S用一个数组来表示，顶点i属于S，则S[i]=1，否则S[i]=0；W是一个二维数组，W[i][j]表示边（i, j）的权。

当(i, j)?E时，W[i][j]可设置为一个大数（比如+∞）；顶点v是源。

Dijkstra算法：
S1. i=1
S2. 若i≤n 转S3，否则转S4
S3. S[i]=0，DIST[i]=W[v, i]，i=i+1 转S2
S4. S[v]=1，DIST[v]=0
S5. i=1
S6. 若i≤n-1 转S7，否则转S11
S7. 选取u，它使
S8. S[u]=1
S9. 对所有S[w]=0的结点作：
若DIST[w] > DIST[u]+W[u][w]，则DIST[w]=DIST[u]+W[u][w]
S10. i=i+1，转S6
S11. 输出DIST
上述算法只求出从源到所有其他各个顶点间的最短路径长度。

如果还要求出相应的最短路径，需修改算法。

请读者自己完成。

对于一个具有n个顶点和e条边的带权有向图，Dijkstra算法的主循环体需要○(n)时间。

这个循环需要执行n-1 次，所以完成循环需要○( n2 ) 。

算法的其他部分所需要的时间不超过○( n2 )，所以Dijkstra算法的时间复杂性为○( n2 )。

例对图4-6中的有向图，表4.7.1列出了应用Dijkstra算法计算从源顶点1到其他顶点间最短路径长度的过程
迭代 S u DIST[2] DIST[3] DIST[4] DIST[5]
初始 {1} - 10 +∞ 30 100
1 {1,2}
2 10 60 30 100
2 {1,2,4} 4 10 50 30 90
3 {1,2,4,3} 3 10 50 30 60
4 {1,2,4,3,5}
5 10 50 30 60
表4.7.1 Dijkstra算法的迭代过程
本小节习题：
(1) 修改Dijkstra算法，使得在求最短路径长度的同时得到这些最短路径。

(2) 用修改后的Dijkstra算法求有向带权图4-7中由顶点1到其他顶点的最短路径长度和最短路径。

.
图4-7 有向带权图。