最小生成树 最优二叉树
最小生成树 定义13.4 T是G=<V,E,W>的生成树 (1) W(T)——T各边权之和 求最小生成树的一个算法 避圈法(Kruskal)设G=<V,E,W>,将G中非环边按权从小 到大排序:e1, e2, …, em. (1) 取e1在T中 (2) 查e2,若e2与e1不构成回路,取e2也在T 中,否则弃e2. (3) 再查e3,…, 直到得到生成树为止.
例 求图的一棵最小生成树.
例 求图的一棵最小生成树.
最优二叉树 定义16.9 设2叉树T 有t片树叶v1, v2, …, vt,权分别为w1, w2, …, wt,称 为T 的权,其中l(vi)是vi 的层数. 在所有有t片树叶,带权w1, w2, …, wt 的2叉 树中,权最小的2叉树称为最优2叉树.
Huffman算法 求最优树的算法—— Huffman算法 给定实数w1, w2, …, wt,且w1w2…wt. (1) 连接权为w1, w2的两片树叶,得一个分支点,其权为w1+w2. (2) 在w1+w2, w3, …, wt 中选出两个最小的权,连接它们对应的顶点(不一定是树叶),得新分支点及所带的权. (3) 重复(2),直到形成 t1个分支点,t片树叶为止.
例 求带权为1, 1, 2, 3, 4, 5的最优树. W(T)=38