itgle.com

图的BFS生成树的树高比DFS生成树的树高()。A.小B、相等C、小或相等D、大或相等

题目
图的BFS生成树的树高比DFS生成树的树高()。

A.小

B、相等

C、小或相等

D、大或相等

相似考题

1.图的BFS生成树的树高比DFS生成树的树高()A.小或相等B.小C.大或相等D.大

2.以下说法不正确的是（）。A连通图G一定存在生成树B连通图G的生成树中一定包含G的所有顶点C连通图G的生成树中不一定包含G的所有边D连通图G的生成树可以是不连通的

3.图通过BFS得到的生成树的树高小于或者等于通过DFS得到的生成树的树高。

4.图的生成树是不唯一的,一个连通图的生成树是一个最小连通子图,n个顶点的生成树有n－1条边,最小代价生成树是唯一的。( )此题为判断题(对，错)。

参考答案和解析
参考答案：C
解释：对于一些特殊的图，比如只有一个顶点的图，其BFS生成树的树高和DFS生成树的树高相等。一般的图，根据图的BFS生成树和DFS树的算法思想，BFS生成树的树高比DFS生成树的树高小。
更多“图的BFS生成树的树高比DFS生成树的树高()。 ”相关问题

  • 第1题：

    最小生成树是指________。

    A．连通网的所有生成树中权值之和最小的生成树

    B．由连通网得到的边数最少的生成树

    C．由连通网得到的顶点数相对较少的生成树

    D．连通网的极小连通子图


    D

  • 第2题：

    图的广度优先生成树的树高比深度优先生成树的树高（)。

    A．小或等于

    B．小

    C．大或相等

    D．大


    A

  • 第3题：

    35、关于连通图，下面说法正确的是：

    A．任意连通图至少有一个生成树

    B．任意连通图至多有一个生成树

    C．无向连通图G的所有生成树中，边的权值总和最小的称为G的最小生成树

    D．无向连通图G的所有生成树中，点的权值总和最小的称为G的最小生成树


    D

  • 第4题：

    下列关于图的表述正确的是__________。

    A．n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为O(n+e)。

    B．图的BFS生成树的树高比DFS生成树的树高：小或相等。

    C．若要求一个稠密图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。

    D．对有向图进行拓扑排序，不能判别其是否有环。


    采用邻接矩阵表示时，其广度优先遍历算法的时间复杂度与 e 无关。;其广度优先遍历和深度优先遍历算法的空间复杂度均为 O(n)。;使用队列对图进行广度优先遍历

  • 第5题：

    对于加权连通图G，求其单起点最短路径过程中构造了一棵树T，下列说法正确的是（）。

    A．T是G的生成树

    B．T是G的最小生成树

    C．T是G的最大生成树

    D．T是G的一棵最小生成树


    T是G的生成树

相关内容