图 - 生成树和最小生成树 - 生成树
树(自由树) 无序树和有根树
自由树 就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根 则成为一棵通常的树)
从根开始 为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序 则它就成为一棵 有序树
在图的应用中 我们常常需要求给定图的一个子图 使该子图是一棵树
生成树
生成树
如果连通图G的一个子图是一棵包含G的所有顶点的树 则该子图称为G的生成树(SpanningTree)
生成树是连通图的包含图中的所有顶点的极小连通子图
图的生成树不惟一 从不同的顶点出发进行遍历 可以得到不同的生成树
深度优先生成树和广度优先生成树
( )生成树的求解方法
设图G=(V E)是一个具有n个顶点的连通图 则从G的任一顶点(源点)出发 作一次深度优先搜索(广度优先搜索) 搜索到的
n个顶点和搜索过程中从一个已访问过的顶点v i 搜索到一个未曾访问过的邻接点v j 所经过的边(v i v j )(共n 条)组成
的极小连通子图就是生成树 (源点是生成树的根)
通常 由深度优先搜索得到的生成树称为深度优先生成树 简称为DFS生成树;由广度优先搜索得到的生成树称为广度优先生成树
简称为BPS生成树
【例】从图G 的顶点v 出发所得的DFS生成树如下图(a) 具体生成过程【 参见动画演示 】 BFS生成树如下图(b) 具
体生成过程【 参见动画演示 】
( )求DFS生成树和BFS生成树算法
只要在DFS(或DFSM)算法的if语句中 在递归调用语句之前加入适当生成边(v i v j )的操作(如将该边输出或保存) 即可得到
求DFS生成树的算法
在BFS(或BFSM)算法的if语句中 加入生成树边(v i v j )的操作 可得到求BFS生成树的算法 【参见练习】
注意
①图的广度优先生成树的树高不会超过该图其它生成树的高度
②图的生成树不惟一 从不同的顶点出发进行遍历 可以得到不同的生成树
生成树的通用定义
若从图的某顶点出发 可以系统地访问到图中所有顶点 则遍历时经过的边和图的所有顶点所构成的子图 称作该图的生成树 (此
定义不仅仅适用于无向图 对有向图同样适用 )
( )若G是强连通的有向图 则从其中任一顶点v出发 都可以访问遍G中的所有顶点 从而得到以v为根的生成树
( )若G是有根的有向图 设根为v 则从根v出发可以完成对G的遍历 得到G的以v为根的生成树
【例】下图中(a)图是以v 为根的有向图 它的DFS生成树和BPS生成树分别如图(b)和(c)所示
( )若G是非连通的无向图 则要若干次从外部调用DFS(或BFS)算法 才能完成对G的遍历 每一次外部调用 只能访问到G的一个
连通分量的顶点集 这些顶点和遍历时所经过的边构成了该连通分量的一棵DFS(或BPS)生成树 G的各个连通分量的DFS(或BFS)生成
树组成了G的DFS(或BFS)生成森林
( )若G是非强连通的有向图 且源点又不是有向图的根 则遍历时一般也只能得到该有向图的生成森林
【例】下图(a)所示的有向图 其DFS和BFS生成森林分别如(b)和(c)所示
lishixinzhi/Article/program/sjjg/201311/23831
