|
树(自由树)无序树和有根树 自由树 就是一个无回路的连通图(没有确定根)(在自由树中选定一顶点做根则成为一棵通常的树) 从根开始为每个顶点(在树中通常称作结点)的孩子规定从左到右的次序则它就成为一棵 有序树 在图的应用中我们常常需要求给定图的一个子图使该子图是一棵树 生成树 生成树 如果连通图G的一个子图是一棵包含G的所有顶点的树则该子图称为G的生成树(SpanningTree) 生成树是连通图的包含图中的所有顶点的极小连通子图 图的生成树不惟一从不同的顶点出发进行遍历可以得到不同的生成树 深度优先生成树和广度优先生成树 ()生成树的求解方法 设图G=(VE)是一个具有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)所示 |
