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

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

题库2022-08-02  35
问题 对有n个结点、e条边且采用数组表示法（即邻接矩阵存储）的无向图进行深度优先遍历，时间复杂度为（ ）
选项
答案 A
解析 本题考查数据结构相关知识，图的存储有两种方式：邻接矩阵，邻接表。邻接矩阵：图的顺序存储，矩阵中a的值定义为：0，两个顶点不相邻，1相邻。邻接表：图的链式存储，对图中每一个顶点建立一个单链表，指示与该顶点邻接的顶点和关联的边或出弧。图的深度优先和广度优先遍历的复杂度：邻接矩阵：矩阵包含n2个元素，在算法中，共n个顶点，对每个顶点都要遍历n次，所以时间复杂度为O(n2)邻接表：包含n个头结点和e个表结点，算法中对所有结点都要遍历一次，所以时间复杂度为O（n+e）
转载请注明原文地址:https://tihaiku.com/congyezige/2418759.html
本试题收录于： 中级 数据库系统工程师题库软件水平考试初中高级分类

中级 数据库系统工程师

软件水平考试初中高级

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