2. 从业资格
  3. 对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，

对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，

练习题库2022-08-02  107
问题 对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为（　　）。A.O（n2）B.O（e2）C.O（n+e）D.O（n*e）
选项 A.O（n2）
B.O（e2）
C.O（n+e）
D.O（n*e）
答案 A
解析 在邻接表中，就是要依次访问每个顶点，然后在每个顶点中依次访问每条边，把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍，所以时间复杂度是O（n+e）。在邻接矩阵中，算法需要遍历邻接矩阵×n个点，所以时间复杂度是O（n×n）。
转载请注明原文地址:https://tihaiku.com/congyezige/2410510.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)