广度优先生成树的高度怎么求
发布网友
发布时间:2022-11-21 17:40
我来回答
共1个回答
热心网友
时间:2024-11-24 19:07
广度优先生成树的高度的求解方法:
1、从G的任一顶点(源点)出发,作一次深度优先搜索广度优先搜索,搜索到的n个顶点和搜索过程中从一个已访问过的顶点vi搜索到一个未曾访问过的邻接点vj,所经过的边vi,vj共n-1条组成的极小连通子图就是生成树,源点是生成树的根。
2、通常由深度优先搜索得到的生成树称为深度优先生成树,简称为DFS生成树,由广度优先搜索得到的生成树称为广度优先生成树,简称为BFS生成树。