离散数学之树和生成树的笔记(下)

离散数学之树和生成树的笔记(下):

  1. 最小生成树
  2. 最优二叉树
  3. 最优二叉树的应用:最佳前缀码

我之前竟然一直把最小生成树和最优二叉树视为同一个东西,真是很糟糕。

最小生成树

最小生成树之目的在于从一个图(带权图,不然“最小”就没有意义了)中产生一个生成树,而使得此生成树中各边权之和最小

Kruskal算法(又称“避圈法”)是求最小生成树的一个比较常见且容易的方法。这个方法大致如下:

  1. 先按权的大小将各边排序:e1,e2,e3,e4,…,em。(这个和求最优二叉树有一点点像)(m是边数)
  2. 先把e1放入最小生成树T里,然后检查e2,如果e2与T中的边不构成回路,则把e2也放入T中,一直检查到em即可。(不能构成回路显然是因为树的定义里规定了树是连通无回路的图)
  3. 如果有环,那么环显然是要去掉的,因为环放进T中的话,自己就形成了一个回路了。

最优二叉树

最优二叉树也很容易求出来。方法叫Huffman算法。与求最小生成树不同,求最优二叉树的时候往往我们知道的东西是“带权某某某的(顶点)”,而实际上求出来的最优二叉树,顶点个数往往会多于我们已知的带权的顶点数目。

  1. 先按权的大小将顶点依次排列。v1, v2, v3, v4……,vm
  2. 然后先给最小的两个顶点一个父亲,使他们成为兄弟,然后把记下父亲的权。返回第二步,把父亲的权计入排序,兄弟的权则不用管了。
  3. 重复第二步的操作。

最优二叉树的应用:最佳前缀码

编码就是将一个符号用一串数字或其它形式来表示。比如说用00表示A,用01表示B等等。

如果a1a2a3a4…..an-1an是一个长度为n的符号串(不是字符串),那么a1a2a3a4…an-1就是这个符号串的子串,称之为前缀。如果有一个集合是A={一个字符串},如果A中的任意两个元素都互不为前缀,则把集合A称为前缀码。只有0、1的称为二元前缀码。

那么最优二叉树有什么用?因为二元前缀码要求的是互不为前缀,而一个2叉树,把走左边的记为0,走右边的记为1,那么显然走到每个树叶所得的代码都不一样,可以形成一个二元前缀码。如果是2叉二叉树(正则指的是每个树叶的层数都为树高),则形成的二元前缀码是唯一的。

而最佳前缀码指的是二进制位数最少,这样能够提高效率。那么这么做的思路就是,让出现概率比较小的字符,用编码较长的符号表示,让出现概率比较大的字符,用编码较短的符号表示。

比如:八个字符出现的概率:

0:25%   1:20%

2:15%   3:10%

4:10%   5:10%

6:5%     7:5%

把频率乘10当做权,这样计算方便一些,然后进入求最优二叉树的方法,得到一个最优二叉树。

然后所需要的二进制数字个数(这里是假设给了100个含有0、1、2、3、4、5、6、7的数组)就等于各个分支点权之和。

不过我还觉得这样求二进制数字个数更好理解啊。就是用数字出现的概率,去乘我们算出来的二进制码的位数。比如说7代表的顶点求出来的二进制码是00000,而100个数字中7出现的概率是5,那么就得出因为7而产生的二进制数字个数为7*5。其它类似,然后求和就可以得到二进制数字的个数了。感觉比求分支点权之和要好理解一些。

留下评论

电子邮件地址不会被公开。 必填项已用*标注