题目内容

对含有n个顶点、e条边的带权图求最短路径的Dijkstra算法的时间复杂度为( )。

A. O(n)
B. O(n+e)
C. O(nn)
D. O(ne)

查看答案

搜索结果不匹配？点我反馈

更多问题

在用邻接表表示有N个结点E条边的图时,深度优先遍历算法的时间复杂度为( ),在用邻接矩阵表示有N个结点E条边的图时,深度优先遍历算法的时间复杂度为( )。

A. O(N*E),O(N*N)
B. O(N+E),O(N*E)
C. O(N+E),O(N*N)
D. O(N*N),O(N*N)

若要检查有向图中有无回路,除了可以利用拓扑排序算法外,下列哪种算法也可以用?

A. 广度优先搜索
B. 深度优先搜索
C. Prim算法
Dijkstra算法

无向图的邻接矩阵是对称矩阵,所以可采用压缩存储法(下三角),其存储空间只需。

对于一个具有n个顶点和e条边的有向图和无向图,在其对应的邻接表中,所含边结点分别有个和个。注意:答案中两个符号相乘,如x与y相乘,直接写为 xy