下列代码片段用于判断有向图是否为强连通图(假设顶点编号从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