Download presentation
Presentation is loading. Please wait.
1
最小生成树 最优二叉树
2
最小生成树 定义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,…, 直到得到生成树为止.
3
例 求图的一棵最小生成树.
4
例 求图的一棵最小生成树.
5
最优二叉树 定义16.9 设2叉树T 有t片树叶v1, v2, …, vt，权分别为w1, w2, …, wt，称 为T 的权，其中l(vi)是vi 的层数. 在所有有t片树叶，带权w1, w2, …, wt 的2叉 树中，权最小的2叉树称为最优2叉树.
6
Huffman算法 求最优树的算法—— Huffman算法 给定实数w1, w2, …, wt，且w1w2…wt. (1) 连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2. (2) 在w1+w2, w3, …, wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权. (3) 重复(2)，直到形成 t1个分支点，t片树叶为止.
7
例 求带权为1, 1, 2, 3, 4, 5的最优树. W(T)=38
Similar presentations
