判断题
偏易
#19775
使用邻接矩阵存储一个有 个顶点、 条边的图,对该图进行一次完整的BFS遍历,时间复杂度为。
使用邻接矩阵存储一个有 个顶点、 条边的图,对该图进行一次完整的BFS遍历,时间复杂度为。
答案与解析
正确答案:错
解析
确定图的顶点数n和边数m;获取邻接矩阵存储结构,其规模为n×n;BFS遍历从起始顶点开始,使用队列管理待访问顶点;每轮取出队首顶点,标记为已访问;遍历该顶点在邻接矩阵中的整行,查找所有邻接且未访问的顶点并加入队列;每一行的检查耗时O(n),最多处理n个顶点;总时间由访问所有顶点和检查所有矩阵元素决定;矩阵中每个元素被访问一次,共n²次操作;最终时间复杂度由顶点数n决定。