题14 题目 图的广度优先生成树的树高比深度优先生成树的树高 ( ). A. 小或相等 B. 小 C. 大或相等 D. 大 分析 对于无向图的广度优先搜索生成树, 起点到其他顶点的路径是图中对应的最短路径, 即所有生成树中树高最小。 此外, 深度优先总是尽可能 “深” 地搜索图, 因此其路径也尽可能长, 所以深度优先生成树的树高总是大于或等于广度优先生成树的树高。 解 A