●若采用邻接矩阵结构存储具有n个顶点的图,则对该图进行广度优先遍历的算法时间复杂度为 (47) 。(4

Question

●若采用邻接矩阵结构存储具有n个顶点的图，则对该图进行广度优先遍历的算法时间复杂度为 (47) 。

(47) A．O(n)

B．O(n2)

C．O(n2+1)

D．以上都不对

Answer 1

正确答案：B
【解析】n个顶点的图的邻接矩阵是一个n阶方阵，有n行n列。从顶点vi出发，对图进行广度优先遍历，需对矩阵的第i行逐列检测非零元(若a[i][j]1,则说明顶点vj与vi之间有边存在，vj就是vi的邻接顶点)。根据广度优先遍历的思想，每一个顶点都要轮换着做出发顶点，即矩阵的每一行都将要被逐列检测。显然，算法中要用一个两重循环来组织逐行逐列的检测操作，所以，算法的时间复杂度是n的平方阶。