离散17有向树.ppt

. -吴扬扬制- * 主要内容： 生成树 基本概念 求最小生成树算法 有向树 最优树 定义 算法 性质 应用-前缀码设计 * §11.7 树 2.生成树(1) 生成树： 定义：若无向图G的生成子图T是树，则称T是G的生成树或支撑树， 生成树T的边称为树枝， G中不在生成树T中的边称为T的弦。 例2： 定理11.7.3 一个连通图G中至少存在一棵生成树。 最小生成树：Prim算法和Kruskal算法 定义：设无向图G=V,E,W是赋权图，T是G的生成树， T的所有树枝的权之和称为T的权W(T), G的生成树中权最小的树称为G的最小生成树。 * §11.7 树 2.生成树(2) 避圈法 设无向连通赋权图G=V,E,W，|V|=n,|E|=m, (1) A:=?; (2) 取e*?E-A使w(e*)=min{w(e)|e?E-A且A?{e}的导出子图无简单回路}， A:=A?{e*}; (3) 若|A|=n-1,则结束，否则转(2). 例3： e1 e2 e4 e3 e5 e6 e7 e8 e9 e10 e11 e12 12 10 6 4 2 9 7 3 1 11 8 5 A e* ? e12 {e12} e5 {e12,e5} e8 {e12, e5, e8, e11} {e12, e5, e8} e11 {e12, e5, e8, e11, e3} {e12, e5, e8, e11, e3, e10} {e12, e5, e8, e11, e3, e10, e6} e3 e10 e6 破圈法? n=8 W(T)=34 . -吴扬扬制- * §11.7 树 2.生成树(3) 破圈法 设无向连通赋权图G=V,E,W，|V|=n,|E|=m, (1) A:=E; (2) 若A的导出子图中无简单回路,则结束； (3) 在A的导出子图中找一条简单回路C,设C中权最大的边为e*; (4) A:=A-{e*},转(2). e1 e2 e4 e3 e5 e6 e7 e8 e9 e10 e11 e12 12 10 6 4 2 9 7 3 1 11 8 5 A e* e1 {e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12} C e1e5e9e6 e2e7e10e6 e2 e9e10e11e12 e9 {e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12} {e3,e4,e5,e6,e7,e8,e9,e10,e11,e12} {e3,e4,e5,e6,e7,e8,e10,e11,e12} e7e3e8e11 e7 {e3,e4,e5,e6,e8,e10,e11,e12} e5e12e8e4 e4 {e3,e5,e6,e8,e10,e11,e12} ?避圈法 . -吴扬扬制- * §11.7 树  3. 有向树 基本概念： 有向树：满足下列条件的有向图称为有向树： (1) 有且仅有一个顶点的入度为0(称之为树根)； (2) 除树根外的顶点入度为1； (3) 从树根到任何顶点均有一条有向通路。 例1： 树叶、内点、分支点 儿子、父结点、兄弟、祖先、后裔 M元树、M元正则树 . -吴扬扬制- * §11.7 树  4.最优树(1) 定义：设2元正则树T的t片树叶，分别带权w1,w2,…,wt,称 其中l(vi)是从树根到树叶vi的通路的长度。 所有带权w1,w2,…,wt的t片树叶的2元正则树中，权最小的树称为 带权w1,w2,…,wt的最优二元树。 例： 7 5 6 10 7 5 6 10 W(T1)=7?2+5?2+6?2+10?2 =56 W(T2)=7?3+5?3+6?2+10?1 =58 是否还有其他带权7, 5,6,10的2元正则树？ 哪棵是带权7,5,6,10 的最优2元树？ . -吴扬扬制- * §11.7 树  4.最优树(2) 求最优树Huffman算法: 给定权w1,w2,…,wt，设w1≤w2≤…≤wt， (1)连接权为w1,w2的2片树叶，得一分支点，其权为w1+w2； (2)从w1+w2,…,wt中选出2个最小权，连接对应顶点，得一分支点及其权； (3)重复(2)，