Question

对有 n 个结点、e 条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度优先遍历, 时间复杂度为( )。

A.O（n^2）
B.O（e2）
C.O（n+e）
D.O（n*e）

Answer 1

【答案】：A
图的邻接矩阵是指用一个矩阵来表示图中顶点之间的关系。对有 n 个结点的图，其邻接矩阵是一个n阶方阵。对于无向图来说，其邻接矩阵如下图所示

当采用深度优先进行遍历的时候，查找所有邻接点所需要的时间是O(n^2) 。