树图与最小生成树

1、16.2 树树图与最小生成树图与最小生成树 一般研究无向图一般研究无向图 树图：倒置的树，树图：倒置的树，根根(root)在上，在上，树叶树叶(leaf)在下在下 多级辐射制的电信网络、管理的指标体系、家谱、分多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图类学、组织结构等都是典型的树图C1C2C3C4根根叶叶2 6.2.1 树的定义及其性质树的定义及其性质 任两点之间有且只有一条路径的图称为任两点之间有且只有一条路径的图称为树树(tree)，记为，记为T 树的性质树的性质： 最少边的连通子图，树中必不存在回路最少边的连通子图，树中必不存在回路 任何树必存在次数为任

2、何树必存在次数为 1 的点的点 具有具有 n 个节点的树个节点的树 T 的边恰好为的边恰好为 n 1 条，反之，任何有条，反之，任何有n 个节点，个节点， n 1 条边的连通图必是一棵树条边的连通图必是一棵树 6.2.2 图的生成树图的生成树 树树 T 是连通图是连通图 G 的的生成树生成树(spanning tree)，若，若 T 是是 G的的子图且包含图子图且包含图 G 的所有的节点；包含图的所有的节点；包含图 G 中部分指定节中部分指定节点的树称为点的树称为 steiner tree 每个节点有唯一标号的图称为标记图，标记图的生成树每个节点有唯一标号的图称为标记图，标记图的生成树称为称为

3、标记树标记树(labeled tree)Caylay 定理定理：n ( 2)个节点，有个节点，有nn 2个不同的个不同的标记树标记树3 6.2.2 图的生成树图的生成树 如何找到一棵生成树如何找到一棵生成树 深探法深探法(depth first search)：任选一点标记为：任选一点标记为 0 点开始搜点开始搜索，选一条未标记的边走到下一点，该点标记为索，选一条未标记的边走到下一点，该点标记为 1，将，将走过的边标记；假设已标记到走过的边标记；假设已标记到 i 点，总是从最新标记的点，总是从最新标记的点向下搜索，若从点向下搜索，若从 i 点无法向下标记，即与点无法向下标记，即与 i 点相关联

4、点相关联的边都已标记或相邻节点都已标记，则退回到的边都已标记或相邻节点都已标记，则退回到 i 1 点继点继续搜索，直到所有点都被标记续搜索，直到所有点都被标记 广探法广探法(breadth first search)：是一种有层级结构的搜索，：是一种有层级结构的搜索，一般得到的是树形图一般得到的是树形图ACDBACDBACDBADCB4 6.2.3 最小生成树最小生成树 有有n 个乡村，各村间道路的长度是已知的，如何敷设光个乡村，各村间道路的长度是已知的，如何敷设光缆线路使缆线路使 n 个乡村连通且总长度最短个乡村连通且总长度最短 显然，这要求在已知边长度的网路图中找最小生成树显然，这要求在已

5、知边长度的网路图中找最小生成树 最小生成树的算法最小生成树的算法： Kruskal 算法：将图中所有边按权值从小到大排列，依算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集次选所剩最小的边加入边集 T，只要不和前面加入的边，只要不和前面加入的边构成回路，直到构成回路，直到 T 中有中有 n 1 条边，则条边，则 T 是最小生成树是最小生成树 Kruskal 算法基于下述定理算法基于下述定理定理定理 3 指定图中任一点指定图中任一点vi，如果，如果 vj 是距是距 vi 最近的相邻节点，最近的相邻节点，则关联边则关联边 eij 必在某个最小生成树中。必在某个最小生成树中。推论推论

6、 将网路中的节点划分为两个不相交的集合将网路中的节点划分为两个不相交的集合V1和和V2，V2=V V1，则，则V1和和V2间权值最小的边必定在某个最小生间权值最小的边必定在某个最小生成树中。成树中。5 6.2.3 最小生成树最小生成树 最小生成树不一定唯一最小生成树不一定唯一 定理定理 3 推论是一个构造性定理，它指示了找最小生成树推论是一个构造性定理，它指示了找最小生成树的有效算法的有效算法 Prim 算法：不需要对边权排序，即可以直接在网路图上算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算操作，也可以在边权矩阵上操作，后者适合计算机运算 边权矩

7、阵上的边权矩阵上的 Prim 算法算法：1、根据网路写出边权矩阵，两点间若没有边，则用、根据网路写出边权矩阵，两点间若没有边，则用 表示；表示；2、从、从 v1 开始标记，在第一行打开始标记，在第一行打 ，划去第一列；，划去第一列；3、从所有打、从所有打 的行中找出尚未划掉的最小元素，对该元素画圈，的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打划掉该元素所在列，与该列数对应的行打 ；4、若所有列都划掉，则已找到最小生成树、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应所有画圈元素所对应的边的边)；否则，返回第；否则，返回第 3 步。步。该算法中，打该算法中，打 行对应的节点在行对应的节点在 V1中，未划去的列在中，未划去的列在 V2中中6 6.2.3 最小生成树最小生成树 97125 .19179810787111275 . 9165 .195 . 9101710111610 Prim算法是多项式算法算法是多项式算法 Prim算法可以求最大生成树算法可以求最大生成树 网路的边权可以有多种解释，如效率网路的边权可以有多种解释，