生成树是否与遍历算法有关

1. 为什么图的bfs生成树的树高比dfs生成树的树小或相等

图的bfs生成树的树高比dfs生成树的树小或相等的原因如下：

1、广度优先搜索（BFS）和深度优先搜索（DFS）是两种常见的图遍历算法。

2、BFS是层序遍历，每次都会把离根节点最近的节点先进行遍历，这样能够保证搜索到的节点数目不会超过树的深度，也就不会超过树的最大高度。

3、DFS是递归进行的，它从根节点开始，沿着一个方向遍历到不能再深入为止，然后回溯到之前的节点，再沿着另一个方向进行遍历。这种方式可能会导致某些节点的多次遍历，尤其是在一些复杂的树或图中，从而增加了生成树的高度。

3、优化问题：在一些需要找出最优解的问题中，如找到一个图中的最大权值或者最大价值，DFS也可以被应用。这是因为DFS在遍历过程中会完整遍历所有的路径，然后回溯并选取最优的解。

4、图的遍历：BFS可以用于遍历图中的所有节点，查找特定节点或找到从起始节点到目标节点的最短路径。

5、搜索最短路径：BFS在寻找最短路径问题上非常有效，因为它会逐层遍历图的节点，直到找到目标节点。

6、图的连通性：BFS可以用于检测图是否连通，以及找到图的连通分量。

7、生成树：在生成树算法中，BFS也被用作一种高效的算法，用于在加权无向图中构造最小生成树。

2. 普里姆算法的相关概念

1）生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连通图的极小连通子图，包含图中的所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个生成森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。
2）和树的遍历相似，若从图中某顶点出发访遍图中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历，(Traversing Graph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS）。对每种搜索顺序，访问各顶点的顺序也不是唯一的。
3）在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G′称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同。
在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。常见的求最小生成树的方法有两种：克鲁斯卡尔(Kruskal)算法和普里姆（Prim）算法。

3. 连通图用深度优先和广度优先算法所得的生成树是否唯一

理论上遍历所得的生成树或序列是不唯一的，算法本身并没有对同等条件下哪个点优先访问做要求。但实际写代码的时候肯定要按某种顺序遍历，通常是从小到大，这时首个访问的点肯定是第一个点，当前点与多个未访问点相连时也是优先访问编号小的点，这样所得的结果就是唯一的了。