图的广度优先生成树的树高比深度优先生成树的树高()。A.小或相等B.小C.大或相等D.大
广度,深度,大图
已帮助 人
-
正确答案:A
对于无向图的广度优先搜索生成树中,起点到其他顶点的路径是图中对应的最短路径,也即是所有生成树中树高最小的。此外,深度优先总是尽可能“深”地搜索图,因此其路径也是尽可能的长,故深度优先生成树的树高总是大于或等于广度优先生成树的树高。
