第九讲 1、图的基本概念复 习 2 、 最小生成树 12最小生成树 最小生成树 1. 1. 生成树 生成树 在一个无向连通图 在一个无向连通图G G中，其所有顶点和遍历该图经过的所有 中，其所有顶点和遍历该图经过的所有 边所构成的子图 边所构成的子图G G 称做图 称做图G G的生成树。一个图可以有多个生成树 的生成树。一个图可以有多个生成树 ，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边 ，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边 也就不同，例如图 也就不同，例如图7-12 7-12的 的( (b) b) 和 和( (c) c) 为图 为图7-12 7-12 ( (a) a) 的两棵生成树。其 的两棵生成树。其 中 中 ( (b) b) 是通过 是通过DFS DFS得到的，称为深度优先生成树； 得到的，称为深度优先生成树；( (c) c) 是通过 是通过BFS BFS 得到的，称为广度优先生成树。 得到的，称为广度优先生成树。 图 图7-12 7-12 生成树 生成树 3 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶 点、n-1 条边。而所有包含
