最小生成树
连通图：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图。
强连通图（Strongly Connected Graph）是指在有向图G中，如果对于每一对vi、vj，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。
示例：
分别使用Kruskal算法和Prim算法，找出下图的最小生成树。
贪心1.jpg
1.Kruskal算法
初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
- 把图中的所有边按代价从小到大排序。
- 列出图中所有的点。
- 按权值从小到大选择边，如果选的边使图中形成环，则舍弃，选择下一条边。例如下图，在第6步中，CD边的权重最小，是3，若选择CD边，则C,D,G形成环，故应该舍弃，因此第7步选择权重为4的AE边。
- 重复(3),直到有n-1条边为止。
贪心2.jpg
2.Prim算法
每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。
1.图的所有顶点集合为V；初始令集合u={A},v=V−u={B,C,D,E,F,G,H}
2.在两个集合u,v能够组成的边中，选择一条代价最小的边(U,V)，加入到最小生成树中，并把V并入到集合u中。
重复上述步骤，直到最小生成树有n-1条边或者n个顶点为止。
贪心3.jpg
贪心1.jpg
解析：
1.初始化u={A}，v={B,C,D,E,F,G,H}。
2.第一次选取，u,v能够组成的边为(A,B),(A,E),(A,F)。B列的(A,1)表示：由A到达B，权重为1。在可达的三条边中，AB的代价最小，将B添加到u中，此时u={A,B}，开始第二次选取。
3.重复第二步，直到所有的顶点都添加到u中为止。
霍夫曼编码
使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。
具体步骤
1.将信源符号的概率按减小的顺序排队。
2.把两个最小的概率相加，并继续这一步骤，始终将较高的概率分支放在右边，直到最后变成概率１。
3.画出由概率１处到每个信源符号的路径，顺序记下沿路径的０和１，所得就是该符号的霍夫曼码字。
4.将每对组合的左边一个指定为0，右边一个指定为1（或相反）。
示例：
假设字符a,b,c,d,e出现的概率分别为1/2,1/4,1/8,1/16,1/16。
1.求出各字符哈夫曼编码表。
2.假设一个文件有1,000,000个字符，求出编码之后文件的字节长度。
贪心4.jpg
A:0
B:10
C:110
D:1110
E:1111
a所占长度l1为：（1,000,000/2）1
b所占长度l2为：（1,000,000/4）2
c所占长度l3为：（1,000,000/8）3
d所占长度l4为：（1,000,000/16）4
e所占长度l5为：（1,000,000/16）*4
文件的总长度l = l1 + l2 + l3 + l4 + l5 = 1875000
网友评论