在一个无向连通图中,从任意顶点开始进行深度优先遍历,最终得到的 DFS 生成树一定包含图中的所有顶 点。
A:正确
B:错误
正确答案:正确
答案解析
深度优先遍历从指定起始顶点出发,沿边访问可达顶点,每条被遍历的边加入生成树。遍历过程中,未访问的相邻顶点被递归访问,直至所有从起始点可达的顶点均被处理。无向连通图中任意顶点对之间存在路径,因此从任一顶点出发的 DFS 可访问全部顶点。生成树由遍历过程中实际使用的边构成,覆盖所有被访问顶点。由于图连通,所有顶点均被访问,故生成树包含全部顶点。遍历顺序不影响顶点覆盖性,只影响边的选择。生成树结构依赖于遍历路径,但顶点集合始终为全集。
试卷来源:202603 CCF-GESP编程能力等级认证C++七级真题