判断题 偏易
#16941

使用邻接矩阵存储一个有 V 个顶点、 E 条边的图,对该图进行一次完整的BFS遍历,时间复杂度为 O(V+E) 。

使用邻接矩阵存储一个有 V 个顶点、E 条边的图,对该图进行一次完整的BFS遍历,时间复杂度为 O(V+E)。

未登录也能判分,登录后才会记录
答案与解析
正确答案:错
解析
BFS遍历从起始顶点开始,使用队列管理待访问顶点。邻接矩阵为V×V二维数组,每行对应一个顶点,元素表示顶点间是否存在边。算法首先初始化所有顶点为未访问状态。将起始顶点标记为已访问并入队。当队列非空时,出队一个顶点,遍历其在邻接矩阵中的对应行,查找所有与其相邻且未访问的顶点,将它们标记为已访问并入队。每个顶点被访问一次,每条边在矩阵中被检查一次。由于需扫描整个矩阵以检测邻接关系,总时间开销由顶点数V和边的检查次数决定。