下列代码片段用于判断有向图是否为强连通图(假设顶点编号从0开始)。已知函数bfs的返回值为1时表示该图强连通。现有某次调用bfs(s, n)的结果始终返回0,但实际该图是强连通的。问题最可能出现在哪一环节? A. 队列初始化时未清空历史数据 B. 标记数组mark的初始化值为非零 C. 修改邻接矩阵g[front][i]导致图结构被破坏 D. 顶点访问计数器ha的位置与判断逻辑错误

答案解析

核心考点:BFS遍历图时的逻辑错误与副作用分析。 解题思路: 1. BFS遍历中修改图结构(如g[front][i]=0)会破坏原始数据,导致后续遍历无法进行。 2. 顶点计数器ha在每次循环中重置为0,导致无法正确统计总访问数。 选项分析: - A错误:队列初始化与历史数据无关,每次调用会重新push起点。 - B错误:mark数组初始化为0是标准做法,与题意矛盾。 - C正确:修改邻接矩阵属于副作用,会破坏图的原始结构,导致后续遍历失效。 - D错误:ha的累加逻辑在循环外,若ha每次循环重置则为错误,但题目未明确此细节。 易错点:容易忽视代码中修改图结构的副作用,误以为D是正确答案。需注意ha的作用域是否在循环外。
正确答案:C
随机推荐
开始刷题