给定图G=(V,E), |V|=n, |E|=m, 遍历其邻接表的时间复杂度为θ( )
n+m
举一反三
内容
- 0
一个有n个顶点e条边的连通图采用邻接表表示，从某个顶点v出发进行广度优先遍历BFS(G，v)，则队列中最多的顶点个数是【___】。
- 1
对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）。
- 2
设无向图G=(V,E)是连通的且|V|=n,|E|=m,若(),则G是树 A: m=n+1 B: n=m+1 C: m D: n>M+1
- 3
e条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是（）。 A: O(n) B: O(e) C: O(n+e) D: O(n×e)
- 4
【判断题】n 个顶点 e 条边的图采用邻接矩阵存储,深度优先遍历算法的时间复杂度为 O(n 2 ) ;若采用邻接表存储时,该算法的时间复杂度为 O(n+e)