1 生成树
生成树 1
回顾 2 口内容1：表达式的（逆)波兰记法 口内容2：二叉搜索树 口内容3：前缀码与Huffman编码
内容1：表达式的（逆）波兰记法 内容2：二叉搜索树 内容3：前缀码与Huffman编码 2 回顾
本节提要 口内容1：生成树及其构造方法 口内容2：最小生成树算法
内容1：生成树及其构造方法 内容2：最小生成树算法 本节提要
生成树 口定义：若图G的生成子图是树，则该子图称为G的 生成树。 口注：含有G的所有顶点的子图称为G的生成子图 口无向图G连通当且仅当G有生成树 口证明（充分性显然）： →注意：若G是有简单回路的连通图，删除回路上的 一条边，G中的回路一定减少。（因此，用“破圈法” 总可以构造连通图的生成树) 口简单无向图G是树当且仅当G有唯一的生成树
生成树 定义：若图G的生成子图是树，则该子图称为G的 生成树。 注：含有G的所有顶点的子图称为G的生成子图 无向图G连通当且仅当G有生成树 证明(充分性显然)： 注意：若G是有简单回路的连通图，删除回路上的 一条边，G中的回路一定减少。(因此，用“破圈法” 总可以构造连通图的生成树) 简单无向图G是树当且仅当 G有唯一的生成树
构造生成树：深度优先搜索 b b a a e d e d
构造生成树：深度优先搜索 a c b e d f a c b e d f